[백준] | JAVA, 자바 | 1343번 - 폴리오미노

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

1343번: 폴리오미노

---

문제 요약 :

민식이는 다음과 같은 폴리오미노 2개를 무한개만큼 가지고 있다. AAAA와 BB

이제 '.'와 'X'로 이루어진 보드판이 주어졌을 때, 민식이는 겹침없이 'X'를 모두 폴리오미노로 덮으려고 한다. 이때, '.'는 폴리오미노로 덮으면 안 된다.

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

 

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

---

문제 풀이 :

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String board = br.readLine();
        int count = 0;
        int game = 0;
        ArrayList<Integer> boards = new ArrayList<>();
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < board.length(); i++) {
            String s = String.valueOf(board.charAt(i));
            if (s.equals("X")) {
                boards.add(1);
            } else {
                boards.add(0);
            }
        }

        for (int i = 0; i < boards.size(); i++) {
            if (boards.get(i) == 1) {
                count++;
            }
            if (boards.get(i) == 0 || i == boards.size() - 1) {
                if (count % 2 != 0) {
                    game = 1;
                    break;
                } else {
                    poliomino(count, sb);
                    if (boards.get(i) == 0) sb.append(".");
                    count = 0;
                }
            }
        }
        
        if (game == 1) {
            System.out.println(-1);
        } else {
            System.out.println(sb);
        }
    }

    static void poliomino (int count, StringBuilder sb) {
        if (count == 0) return;

        if (count % 4 == 0 || count % 4 == 2) {
            int n = count / 4;
            sb.append("AAAA".repeat(n));
            count = count % 4;
        }
        if (count % 2 == 0) {
            int n = count / 2;
            sb.append("BB".repeat(n));
            count = count % 2;
        }
        poliomino(count, sb);
    }
}

 

1. 보드판의 단어를 입력받기

2. 입력받은 보드판을 for문을 사용해 "X" 면 1, "." 이면 0으로 변환

3. 1과 0으로 변환한 보드판을 확인해서 1이면 count 증가

4. 0이거나 i가 마지막 숫자라면 if문을 통해 조건을 확인

5. count가 2로 나누어떨어지지 않는다면 game을 1로 변경하고 for문 종료

6. count가 2로 나누어떨어진다면 폴리오미노 함수를 호출하고 "." 을 추가, count를 0으로 초기화

6 - 1. 폴리오미노 함수를 호출하고 count 값을 넘겨주었을 때 count가 0이면 종료

6 - 2. 0이 아니면 count를 4로 나누었을 때 0이거나 2가 남는다면 n에 count를 4로 나눈 횟수를 저장

6 - 3. StringBuilder를 사용해 "AAAA" 를 n 만큼 추가, count를 4로 나눈 나머지 저장

6 - 4. count가 2로 나누어떨어진다면, n에 count를 2로 나눈 횟수를 저장

6 - 5. StringBuilder를 사용해 "BB" 를 n 만큼 추가, count를 2로 나눈 나머지 저장

6 - 6. 폴리오미노 함수를 재 호출

7. 만약 game이 1이라면 -1을 출력, 1이 아니라면 sb 출력

---

리팩토링

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

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

        System.out.println(result);
    }

    static String poliomino(String board) {
        String result = "";
        String A = "AAAA", B = "BB";

        result = board.replaceAll("XXXX", A);
        result = result.replaceAll("XX", B);

        if (result.contains("X")) result = "-1";

        return result;
    }
}

 

1. 보드판의 단어를 입력받기

2. 폴리오미노 함수 호출

2 - 1. replaceAll을 사용해 단어 변경

2 - 2. contains로 result에 X가 남아있다면 -1로 변경

2 - 3. result 리턴

3. 수정된 result 출력

 

처음 풀면서 "X" 와 "." 을 1과 0으로 변환할 필요는 없지만 이 방법이 좀 더 편할 것 같아서 작성했었다. 하지만 코드를 수정할 수 있다면 수정해야겠다는 생각을 했었고 다른 사람들은 어떻게 풀었는지 확인해 보던 차 replaceAll을 사용하면 코드가 엄청 간략해지는 것을 확인할 수 있었다.

replaceAll 메서드는 문자열 안에 있는 특정 패턴을 다른 문자열로 치환하는 데 사용한다.

contains 메서드는 문자열 안에 특정 문자열 또는 서브스트링이 포함되어 있는지 확인하는데 사용한다.

replaceAll을 통해 "XXXX" , "XX" 를 "AAAA", "BB"로 치환해 주고 contains를 사용해 "X"가 남아 있는지 확인한다.

 

처음 코드 메모리 14184 KB, 시간 124ms, 코드길이 1771B

수정 후 코드 메모리 14260KB, 시간 124ms, 코드길이 666B

---

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

public class Main {
    public static int N;
    public static char[] map;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        map = st.nextToken().toCharArray();

        for (int i = 0; i < map.length;) {
            if (i + 3 < map.length && map[i] == 'X' && map[i + 1] == 'X' && map[i + 2] == 'X' && map[i + 3] == 'X') {
                map[i] = 'A';
                map[i + 1] = 'A';
                map[i + 2] = 'A';
                map[i + 3] = 'A';
                i += 4;
            } else if (i + 1 < map.length && map[i] == 'X' && map[i + 1] == 'X') {
                map[i] = 'B';
                map[i + 1] = 'B';
                i += 2;
            } else {
                i++;
            }
        }

        for (char value : map) {
            if (value == 'X') {
                System.out.println("-1");
                return;
            }

        }
        
        for (char value : map) {
            System.out.print(value);
        }
    }
}

 

1343번 문제는 알고리즘 분류가 그리디 알고리즘으로 분류되어 있는데 앞서 풀었던 방식은 그리디 알고리즘을 사용했다고 보기 힘들다. 그래서 그리디 알고리즘을 사용한 코드를 작성해 보았다.