백준 1343 폴리오미노 문제풀이 (JAVA)

문제 링크

문제

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

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

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

입력

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

출력

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

풀이

처음에 '.'이 나올 때까지('X'가 나오는 동안) X의 개수를 센다.
만약 '.'이 나왔을 때 X의 값이 홀수이면 AA, BBBB로는 채울 수 없으니 -1을 출력한다.
만약 짝수이면, X의 개수가 4개 이상이면 4개 미만이 될 때 까지 AAAA로 채우고, 맨 마지막에 AAAA로 못채울 때 (X가 2개밖에 남지 않을 때) BB로 채운다.
맨 마지막에 .으로 끝나지 않아 마지막 부분을 출력을 못할 수 있다.polyCount가 0이 아니면 아직 출력이 끝나지 않은 것을 뜻하니 나머지 값들을 출력해준다.

소스코드

import java.util.*;
import java.io.*;
public class Main{
    
    public static void main(String [] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        final String input = br.readLine();
        int polyCount = 0;
        for(int i=0;i<input.length();i++) {
            if(input.charAt(i)=='X') {
                polyCount++;
            }else {
                if(polyCount%2 == 1) {
                    sb = new StringBuilder();
                    sb.append(-1);
                    break;
                }
                
                while(polyCount != 0) {
                    if(polyCount >= 4) {
                        sb.append("AAAA");
                        polyCount -= 4;
                    }else{
                        sb.append("BB");
                        polyCount -= 2;
                    }    
                }
                
                  sb.append(".");
                                
            }
        }
        if(polyCount > 0) {
            if(polyCount%2 == 1) {
                sb = new StringBuilder();
                sb.append(-1);
            }else {
                while(polyCount != 0) {
                    
                    if(polyCount >= 4) {
                        sb.append("AAAA");
                        polyCount -= 4;
                    }else {
                        sb.append("BB");
                        polyCount -= 2;
                    }   
                }
            }
            
           
        }
        
        sb.append("\n"); 
        
        bw.write(sb.toString());
        
        bw.flush();
        br.close();
        bw.close();
        
    }

    
}