[자바]백준 1343번 폴리오미노 [그리디][엄탱]

안녕하세요. 개발자 엄탱입니다.
이 글은 알고리즘을 공부하면서 공부 기록용입니다.
그래서 설명마다 일기용으로 편하게 작성하여 반말 형식으로 작성하려고 합니다.
그리고 보시다가 더 좋은 방법이나 잘 못 알고 있는 내용이 있다면 알려주시면 정말 감사하겠습니다.
좋은 하루 되세요 :)

 

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

1343번: 폴리오미노

 

문제

민식이는 다음과 같은 폴리오미노 2개 AAAA와 BB를 무한개만큼 가지고 있다.
이제 '.'와 'X'로 이루어진 보드판이 주어졌을 때, 민식이는 겹침 없이 'X'를 모두 폴리오미노로 덮으려고 한다.
이때, '.'는 폴리오미노로 덮으면 안 된다.

폴리오미노로 모두 덮은 보드판을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 보드판이 주어진다. 보드판의 크기는 최대 50이다.

출력

첫째 줄에 사전순으로 가장 앞서는 답을 출력한다. 만약 덮을 수 없으면 -1을 출력한다.

 

예제 입력 1

XX.XXXXXXXXXX..XXXXXXXX...XXXXXX

예제 출력 1

BB.AAAAAAAABB..AAAAAAAA...AAAABB

예제 입력 2

XXXX....XXX.....XX

예제 출력 2

-1

 

알고리즘 분류

• 구현
• 그리디 알고리즘

 

문제 설명

X를 남김없이 아래 방식으로 치환해야 하는 문제다.

XXXX를 AAAA로 XX를 BB로 치환하면 된다.

출력은 사전순으로 출력하라고 적혀있다.

마침표(.)는 그대로 출력하면 된다.

X가 남아있으면 -1 출력

 

해설

간단한 방법

가장 간단한 방법은 replace로 XXXX를 AAAA로 XX를 BB로 치환 후 X가 남아있지 않으면 치환한 문자를 출력 남아있다면 -1을 출력하면 된다.

 

하지만 위와 같이 하면 공부가 안될 것 같아서 다른 방법으로 구현했다.

 

다른 방법

1.  우선 '.'를 기준으로 문자열을 분리
2.  각각의 분리된 문자열을 검사
3. 문자열이 홀수면 -1 출력 (AAAA, BB는 둘 다 짝수이기 때문)
4. AAAA와 BB로 바꿔주기
5. 뒤 마침표 붙여주기

추가적으로 마침표(.)를 기준으로 문자열을 분리하면 마침표가 뒤에 붙으면(XXXX...) 뒤에 마침표는 문자열에 포함이 안돼서 뒤에 나머지 마침표들이 있다면 나머지 마침표들만 붙여 주면 된다.

 

import java.io.BufferedWriter;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

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

        String ss = br.readLine();
        String[] xs = ss.split("\\.");
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < xs.length; i++) {
            String x = xs[i];

            if (x.length() % 2 != 0) {
                sb = new StringBuilder("-1");
                break;
            } else if (x.length() % 4 == 0) {
                sb.append("AAAA".repeat(x.length() / 4));
            } else {
                sb.append("AAAA".repeat(x.length() / 4));
                sb.append("BB");
            }

            if (i != xs.length - 1) {
                sb.append(".");
            }
        }

        String ans = sb.toString();
        if (!ans.equals("-1")) {
            sb.append(".".repeat(ss.length() - sb.toString().length()));
        }

        bw.write(sb + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}