[자바] 백준 1343 - 폴리오미노 (java)

 문제 : boj1343

---

 

필요 알고리즘 개념

• 그리디
  • 사전순으로 가장 앞서는 답을 출력해주기 위해, 각 연속된 X 집합들의 갯수를 기준으로 최대한 AAAA를 앞에 나오도록 해야 한다. 이런식으로 일정한 규칙을 정해 적용시키다보면 답이 나오는 그리디 문제이다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  '.'은 답을 구하는데 영향을 끼치지 않는다. 연속된 'X' 집합만 생각해보자. 다음을 생각해보자.

...XXXXXXXXXX...XXXXXXXX..XX..XXX

 

  위에서 중요한건 연속된 'X' 집합의 각 갯수이다. 위의 경우라면, 각각 10개, 8개, 2개, 3개가 된다.

10, 8, 2, 3개를 각각 AAAA와 BB를 가지고 어떻게 변경해야 할까? 가장 중요한건 '사전순으로 가장 앞서는 답' 부분이다. 즉, AAAA가 항상 앞에 오는게 이득이다. 그리고 어차피 A는 4개가 연속되야 하고 B는 2개가 연속되어야 하므로(만약 AAAAA, BBB 이런식으로 서로소였다면 이런 방식으로 풀 수 없다.) 단순하게 A를 놓을 수 있는만큼 놓고, 나머지를 B로 채워주면 된다.

 

  수학적으로는 연속된 X의 집합이 N개일 경우, N/4(내림) 번 'AAAA'를 채우고, 나머지를 'BB'로 채우면 된다. 그리고 A와 B가 모두 짝수이므로 하나라도 N이 홀수인게 보이면 바로 -1을 출력해주면 된다.

10개 -> N/4(내림) = 2 이므로 AAAA AAAA 그리고 남은걸 B로 채우면 AAAA AAAA BB

8개 -> N/4(내림) = 2 이므로 AAAA AAAA 그리고 남은건 없다.

2개 -> N/4(내림) = 0이므로 B만 채우면 된다. BB

3개 -> 홀수이므로 불가능하다. 따라서 -1을 출력해주면 된다.

 

  일단 로직은 위와 같고, 문제는 구현을 좀 꼼꼼하게 해야한다. 실수하기 쉽다. 특히 시작이 '.'인 경우와 끝이 '.'인 경우를 주의해야한다.

 

---

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main {
    private boolean checkAndSet(ArrayList<Integer> x, ArrayList<Integer> dot, char c, int cnt) {
        if (c=='X' && cnt%2==1) {
            return false;
        }
        if (c == 'X') x.add(cnt);
        else dot.add(cnt);
        return true;
    }
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        ArrayList<Integer> x = new ArrayList<>();
        ArrayList<Integer> dot = new ArrayList<>();
        int cnt = 1;
        char c = s.charAt(0);
        for (int i = 1; i < s.length(); i++) {
            char cur = s.charAt(i);
            if (c == cur) {
                cnt++;
                continue;
            }
            if (!checkAndSet(x, dot, c, cnt)) {
                System.out.println(-1);
                return;
            }
            c = cur;
            cnt = 1;
        }
        if (!checkAndSet(x, dot, c, cnt)) {
            System.out.println(-1);
            return;
        }

        StringBuilder sb = new StringBuilder();
        if (x.size()==0) {
            for (int i = 0; i < dot.get(0); i++) sb.append('.');
            System.out.println(sb);
            return;
        }
        int dotIdx = 0;
        if (s.charAt(0) == '.') {
            for (int i = 0; i < dot.get(dotIdx); i++) sb.append('.');
            dotIdx++;
        }
        for (int i = 0; i < x.size(); i++) {
            int cur = x.get(i);
            for (int j = 0; j < cur/4*4; j++) sb.append('A');
            cur%=4;
            for (int j = 0; j < cur; j++) sb.append('B');
            if (dotIdx < dot.size()) {
                for (int j = 0; j < dot.get(dotIdx); j++) sb.append('.');
                dotIdx++;
            }
        }
        System.out.println(sb);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}