/<BOJ 백준 1343번> 폴리오미노 - Java

문제 1343번 : 폴리오미노

문제 해설

문제의 출력으로 "사전순으로 가장 앞서는 답을 출력한다." 라고 되어있으므로 여러 가지 정답 중 AAAA가 최대한 많이 나오는 경우가 정답이다. 

 

AAAA와 BB는 각각 4개와 2개의 알파벳으로 구성되어있으므로 입력으로 받는 X의 개수의 총합 또한 짝수가 되어야 한다. X의 개수가 홀수인 경우 폴리오미노를 덮을 수 없어 -1을 출력한다. 문제 해결 아이디어는 다음과 같다.

1. X의 개수를 세어 짝수인지 홀수인지 확인한다.
1-1. X의 개수가 홀수이면 -1을 출력하고 종료한다.
2. X의 개수가 4 이상이라면 폴리오미노 AAAA로 덮기 위해 X의 개수에서 4만큼 차감한다.
3. X의 개수가 2 이상이라면 폴리오미노 BB로 덮기 위해 X의 개수에서 2만큼 차감한다.
4. 2번과 3번의 과정을 X의 개수가 0이 될때까지 계속 반복한다.

 

이를 코드로 구현하면 다음과 같다.

 

for (char c : board.toCharArray()) {
    if (c == 'X') {
    	xCount++;
    } else {
    	if (xCount % 2 != 0) {
    		System.out.println("-1");
    		return;
    }

    	while (xCount >= 4) {
    		sb.append("AAAA");
    		xCount -= 4;
    	}

    	while (xCount >= 2) {
    		sb.append("BB");
    		xCount -= 2;
    	}

    sb.append(".");
    }
}

 

for-each문에 있는 board는 입력값을 String으로 저장한 변수 이름이고 sb는 출력값을 나타내기 위한 StringBuilder의 변수 이름이다. 위 코드의 경우 입력에 dot(.)이 포함되어 있는 경우에만 처리할 수 있다. 따라서 입력에 "XXXXXX"와 같이 dot(.)이 없고 X로만 구성되어 있는 경우에도 따로 처리를 해야한다. 처리 과정은 위 코드와 동일하다. 글 하단 코드에서 확인할 수 있다. 

 

위 과정은 board의 길이를 N, xCount의 개수를 M이라고 가정할 때 O(N * M)의 시간복잡도를 갖는다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

    public void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String board = br.readLine();
        StringBuilder sb = new StringBuilder();
        int xCount = 0;

        for (char c : board.toCharArray()) {
            if (c == 'X') {
                xCount++;
            } else {
                if (xCount % 2 != 0) {
                    System.out.println("-1");
                    return;
            }

            while (xCount >= 4) {
                sb.append("AAAA");
                xCount -= 4;
            }

            while (xCount >= 2) {
                sb.append("BB");
                xCount -= 2;
            }

            sb.append(".");
            }
        }

        if (xCount > 0) {
            if (xCount % 2 != 0) {
                System.out.println("-1");
                return;
            }

            while (xCount >= 4) {
                sb.append("AAAA");
                xCount -= 4;
            }

            while (xCount >= 2) {
                sb.append("BB");
                xCount -= 2;
            }
        }
        System.out.println(sb);

    }

    public static void main(String[] args) throws Exception {
    	new Main().solution();
    }
}