[알고리즘-자바] 백준 1343번 폴리오미노

문제

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

1343번: 폴리오미노

언어

자바 Java

로직

주어진 문자열은 'X'와 '.'이 섞여있습니다. 문제를 해결할 때는 'X'에 대해서만 처리하면 되지만, 최종 출력할 때는 '.'도 같이 출력해야 합니다. 

 

문자열 분리

정규표현식을 사용하여 'X'와 '.'을 분리해줍니다. 정규표현식 "\\.+"의 경우 1개 이상의 '.'을 기준으로 분리해줍니다. 생성자의 인자로  true를 넘겨주었는데, 이는 정규표현식으로 사용된 문자도 포함할 것인지를 의미합니다. 우리는 최종 출력에서 '.' 문자도 출력해야하기 때문에 true를 넘겨줍니다.

StringTokenizer st = new StringTokenizer(br.readLine(), "\\.+", true);

폴리오미노 수행

일단 저장된 토큰 개수만큼 반복문을 수행해야 합니다.

while (st.hasMoreTokens()) {
   ...
}

가장 먼저 토큰을 꺼내줍니다. 이 토큰이 'X'를 포함하는 토큰인지 '.'를 포함하는 토큰인지 확인해야 합니다. '.'의 경우에는 최종 출력에 포함해야 하기 때문에 buffer에 추가해줍니다.

String token = st.nextToken();
if (token.contains(".")) {
    sb.append(token); // sb는 StringBuilder
    continue;
}

문자열의 경우 불변 객체입니다. 문자열을 수정하는 경우 새로운 문자열을 생성하는 시간이 발생하기 때문에 효율적이지 않습니다. 따라서 문자열의 길이를 기준으로 폴리오미노를 수행합니다.

int length = token.length();

토큰의 길이가 짝수가 아닌 경우 "AAAA", "BB" 둘 중 하나로 변경할 수 없습니다. 이는 폴리오미노로 덮은 보드판이 될 수 없음을 의미하기 때문에 -1을 출력하고 반복문을 종료합니다.

 

토큰의 길이가 짝수인 경우 "AAAA", "BB" 둘 중 하나로 변경해야 합니다. 문자열의 길이가 4인경우 "AAAA"가 될 수도 있고, "BBBB"가 될 수도 있습니다. 그러나 문제의 출력을 보면 사전순으로 출력하라고 했기 때문에 "AAAA"가 되는 것이 맞습니다. 따라서 토큰의 일부를 "AAAA"로 바꿀 수 있다면 이를 먼저 수행하고, 그렇지 않다면 "BB"로 바꾸는 작업을 수행합니다. 토큰의 일부를 "AAAA" 또는 "BB"로 변경했다면 토큰의 길이를 변경한 길이만큼 빼줍니다. 이 과정을 반복하면서 토큰의 길이가 0이 된다면 반복문을 종료합니다.

while (true) {
    if (length == 0)
        break;
    if (length % 2 != 0) {
        System.out.println(-1);
        return;
    } else {
        if (length >= 4) {
            length -= 4;
            sb.append("AAAA");
        } else if (length >= 2) {
            length -= 2;
            sb.append("BB");
        }
    }
}

---

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        StringTokenizer st = new StringTokenizer(br.readLine(), "\\.+", true);
        while (st.hasMoreTokens()) {
            String token = st.nextToken();
            if (token.contains(".")) {
                sb.append(token);
                continue;
            }

            int length = token.length();
            while (true) {
                if (length == 0)
                    break;
                if (length % 2 != 0) {
                    System.out.println(-1);
                    return;
                } else {
                    if (length >= 4) {
                        length -= 4;
                        sb.append("AAAA");
                    } else if (length >= 2) {
                        length -= 2;
                        sb.append("BB");
                    }
                }
            }
        }

        System.out.println(sb);
    }
}