[알고리즘 문제] 백준1343 - 폴리오미노

문자열 처리하는 문제인데, 생각보다 시간이 오래걸린 것 같다.

 

가장 중요한 부분은 폴리오미노, "AAAA","BB"의 크기가 모두 짝수이기 떄문에 "X"의 개수가 홀수이면 -1를 출력해야 한다.

"X"의 개수는 "."을 기준으로 각각 몇개있는지 구할 수 있으며, XXXX....XXX.....XX에서 4개,3개,2개가 된다. 여기서 홀수개가 나왔기 때문에 -1을 출력하게 된다.

 

또한, X의 개수를 세다가 "."가 나오면 그때 "X"를 "AAAA"나 "BB"로 바꿔줘야 한다.  그리고 문제에서 "."은 덮으면 안된다고 했으니, 구한 문자열에 "."를 더해준다.

 

그리고 "X"를 "AAA"나 "BB"로 바꿔주는 부분은 print()함수가 맡고 있으며, 인자로 size를 받는다. 인자는 문자열에서 "."로 구분된 각각의 "X"의 개수이다. 여기 들어오는 인자를 모두 짝수이며, 홀수인 경우 print()가 불려지기 전에 모두 거른다. 문제에서 사전순으로 가장 앞서는 답을 출력해야 하기 때문에 가능한 "AAAA"를 먼저 출력한고 "BB"를 출력한다. 

 

while()문으로 size가 0보다 클떄까지 반복하는데 size가 4보다 큰 경우는 "AAAA"를 더하고 4 이하인 경우는 "BB"를 더한다.

 

그리고 문자열의 마지막 문자가 "X"인 경우, "X"의 개수가 홀수이면 -1 짝수이면 print()함수를 호출한다.

 

import java.util.*;

public class Main {

    static String result = "";

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        String s = sc.next();

        if (s.equals("X")) {
            System.out.println(-1);
            return;
        }

        char c;
        int count = 0;

        for (int i = 0; i < s.length(); i++) {
            c = s.charAt(i);
            if (c == 'X') {
                count++;
                if (i == s.length() - 1) {
                    if (count % 2 == 1) {
                        System.out.println(-1);
                        return;
                    } else {
                        print(count);
                    }
                }
            } else if (c == '.') {
                if (count % 2 == 1) {
                    System.out.println(-1);
                    return;
                } else {
                    print(count);
                    result += ".";
                    count = 0;
                }
            }
        }
        System.out.println(result);
    }

    static void print(int size) {
        while (size > 0) {
            if (size >= 4) {
                result += "AAAA";
                size -= 4;
            } else {
                result += "BB";
                size -= 2;
            }
        }
    }
}