[알고리즘-PS] 백준 1343번 폴리오미노 자바 문제풀이

문제

해당 포스팅은 백준의 1343번 폴리오미노 의 접근과 해결 방법을 설명한 글 입니다.
정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.

1343번: 폴리오미노

 

이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자.

 

문제 접근

 

이 문제는 전형적인 그리디 알고리즘을 이용해서 해결할 수 있는 그리디 기초 문제이다.

 

해결법

 

입력이 들어올 때, AAAA 를 먼저 채우는 것이 사전순 앞으로 오는 정답이 되기 때문에 AAAA 가 먼저 채워지는지 검사하고, 그 다음으로 BB 를 검사하는 방식으로 문자열을 마지막까지 iteration 하면 된다.

 

정답 코드

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

        char[] board = br.readLine().toCharArray();

        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < board.length; i++) {
            if(i + 3 < board.length) {
                boolean four = board[i] == board[i + 1] && board[i] == board[i + 2] && board[i] == board[i + 3];

                if(four && board[i] == 'X') {
                    i += 3;
                    sb.append("AAAA");
                    continue;
                }
            }

            if(i + 1 < board.length) {
                boolean two = board[i] == board[i + 1];

                if(two && board[i] == 'X') {
                    i += 1;
                    sb.append("BB");
                    continue;
                }
            }

            if(board[i] == '.') {
                sb.append(".");
            }else {
                sb = new StringBuilder("-1");
                break;
            }
        }
        bw.write(sb.toString());

        bw.flush();
        bw.close();
    }
}

---

정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.