[BOJ] 1343 폴리오미노 - JAVA

1. 문제

1343번: 폴리오미노

민식이는 다음과 같은 폴리오미노 2개를 무한개만큼 가지고 있다. AAAA와 BB

이제 '.'와 'X'로 이루어진 보드판이 주어졌을 때, 민식이는 겹침없이 'X'를 모두 폴리오미노로 덮으려고 한다. 이때, '.'는 폴리오미노로 덮으면 안 된다.

폴리오미노로 모두 덮은 보드판을 출력하는 프로그램을 작성하시오.

 

첫째 줄에 보드판이 주어진다. 보드판의 크기는 최대 50이다.

첫째 줄에 사전순으로 가장 앞서는 답을 출력한다. 만약 덮을 수 없으면 -1을 출력한다.

---

2. 풀이

1.  입력받은 보드판을 char배열로 만든다.

2.  보드판을 한 칸씩 탐색한다.

2-1.  '.'이면 다음 칸 탐색으로 넘어간다.(continue)

2-2.  next변수를 사용해서 현재 i부터 몇 번째 칸까지 'X'인지 체크한다. 이때, next는 4미만이어야 한다.(A가 네 글자)

2-3.  만약 next가 2라면 두 칸을 B로 채운다.

2-4.  만약 next가 4라면 네 칸을 A로 채운다.

2-5.  만약 next가 1,3이라면 -1을 출력하고 프로그램을 종료한다.

2-6.  다음 탐색을 위해 i에 next-1을 저장한다. -1을 하는 이유는 for문 시작지점에서 i++을 하기 때문이다.

3.  탐색이 끝났다면 StringBuilder를 활용해 board를 출력한다.

import java.io.*;

public class BOJ_1343_폴리오미노 {
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      char[] board = in.readLine().toCharArray();

      int next;
      for(int i=0;i<board.length;i++){
         if(board[i]=='.') continue;

         next = 1;
         while(i+next<board.length && next<4 && board[i+next]=='X'){
            next++;
         }

         if(next==2) for(int j=i;j<i+next;j++) board[j] = 'B';
         else if(next==4) for(int j=i;j<i+next;j++) board[j] = 'A';
         else {
            System.out.println(-1);
            return;
         }

         i += next - 1;
      }

      StringBuilder sb = new StringBuilder();
      for(char ch:board) sb.append(ch);
      System.out.println(sb);
   }
}

---

3. 결과

본문 방법 외에 replaceAll을 사용할 수도 있다. 하지만 그건 전체적으로 탐색을 두 번(XXXX, XX)하게 되기 때문에 본문 방식이 좀 더 빠르다.