[JAVA] 백준_1343 폴리오미노

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

📌 문제 탐색하기

 XXXX를 AAAA으로 XX를 BB으로 바꿔서 모든 X를 없애고 사전으로 앞에 있는것을 덮는 문제 조건입니다.
X는 반드시 AAAA나 BB으로만 덮어야 하고 . ( 온점) 은 절대로 덮을 수 없다.
. (온점)이 나와서 덮을 수 없는 경우는 -1을 출력해야합니다.

📌 가능한 시간복잡도

입력받은 문자열의 길이 N에서 문자열 전체를 체크하면서 .(온점) ,(쉼표) X 를 처리한다. split() 함수는 내부적으로 문자열을 순회하면서 동작하고 각각의 블록에서 길이에 따라 repeat()으로 문자열을 붙이기 때문에 가능한 시간복잡도는 O(N)입니다.

📌 코드 설계하기

. (온점)을 기준으로 문자열을 분할하고 각각의 덩어리에서 길이가 2의 배수인지 체크한다. 
최대한 앞부터 AAAA으로 채우고 나머지 2칸은 BB으로 채워주기.

 

📌 정답 코드

import java.io.*;

public class Main {

    public static String solution(String board) {
        StringBuilder result = new StringBuilder();
        String[] blocks = board.split("\\.");

        for (int i = 0; i < blocks.length; i++) {
            String block = blocks[i];
            int len = block.length();

            if (len % 2 != 0) {
                return "-1"; // 덮을 수 없음
            }

            int aCount = len / 4;
            int bCount = (len % 4) / 2;

            result.append("AAAA".repeat(aCount));
            result.append("BB".repeat(bCount));

            if (i < blocks.length - 1) {
                result.append(".");
            }
        }

        int dotCount = 0;
        for (int i = board.length() - 1; i >= 0 && board.charAt(i) == '.'; i--) {
            dotCount++;
        }
        result.append(".".repeat(dotCount));

        return result.toString();
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String board = br.readLine();
        System.out.println(solution(board));
    }
}