백준 1343번: 폴리오미노

https://www.acmicpc.net/problem/1343

 

X와 .으로 이루어진 보드에 폴리오미노 AAAA, BB를 겹치지 않게 X를 덮을 때 사전 순으로 가장 앞서는 경우를 출력하는 문제이다. 연속된 X의 구간이 각각의 두 폴리오미노의 길이 혹은 길이의 합인 짝수가 아닌 경우에는 덮을 수 없으므로 -1을 출력하게 된다.

 

X 구간을 찾기 위해 보드의 맨 앞부터 끝까지 순회하면서 .을 만나면, 구간의 길이를 구한다. 구간의 길이가 홀수라면 덮을 수 없으므로 -1을 출력하고 return 한다. 아니라면 사전 순으로 앞서는 AAAA를 놓을 수 있는 만큼 놓은 후 BB를 놓는다. 그 후, .을 추가해 준 후, 구간의 시작 지점을 다음 순회 위치로 변경해 준다.

int index = 0;
StringBuilder sb = new StringBuilder();
for (int i = 0; i < input.length(); i++) {
    if (input.charAt(i) == '.') {
        int length = i - index;
        if (length % 2 != 0) {
            System.out.print("-1");
            return;
        }
        for (int j = 0; j < length / 4; j++) {
            sb.append(firstPolyomino);
        }
        if (length % 4 == 2) {
            sb.append(secondPolyomino);
        }
        index = i + 1;
        sb.append(".");
    }
}

 

 

마지막 X 구간도 동일하게 구간의 길이 확인 후, AAAA, BB를 사전 순으로 배치한다.

int length = input.length() - index;
if (length % 2 != 0) {
    System.out.print("-1");
    return;
}
for (int j = 0; j < length / 4; j++) {
    sb.append(firstPolyomino);
}
if (length % 4 == 2) {
    sb.append(secondPolyomino);
}

 

 

결과 코드는 다음과 같다.

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

public class 폴리오미노1343 {
    
    private static final String firstPolyomino = "AAAA";
    private static final String secondPolyomino = "BB";
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = br.readLine();
        br.close();
        int index = 0;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < input.length(); i++) {
            if (input.charAt(i) == '.') {
                int length = i - index;
                if (length % 2 != 0) {
                    System.out.print("-1");
                    return;
                }
                for (int j = 0; j < length / 4; j++) {
                    sb.append(firstPolyomino);
                }
                if (length % 4 == 2) {
                    sb.append(secondPolyomino);
                }
                index = i + 1;
                sb.append(".");
            }
        }
        int length = input.length() - index;
        if (length % 2 != 0) {
            System.out.print("-1");
            return;
        }
        for (int j = 0; j < length / 4; j++) {
            sb.append(firstPolyomino);
        }
        if (length % 4 == 2) {
            sb.append(secondPolyomino);
        }
        System.out.print(sb);
    }
}