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

백준(baekjoon) 1343 폴리오미노

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

1343번: 폴리오미노

시간	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	128 MB	12349	6585	5572	53.224%

문제

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

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

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

입력

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

출력

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

 

 

문제 풀이

처음 풀었을 때 굉장히 헷갈렸다. 여러 번 시도를 하였고 난이도에 비해 생각보다 매우 힘겹게 풀었다.

 

내가 시도하였다가 실패한 방법들도 기재하겠다.

1. StringTokenizer

StringTokenizer을 사용하여 .을 만났을 때를 기준으로 나눠야 하나? 라는 생각으로 시도하였으나, 나누는 것은 할 수 있지만 .과 함께 출력해야 하므로 안된다고 결론을 내었다.

 

2. Stack

예전에 이와 유사한 문제를 Stack을 사용하여 풀었던 경험이 있다. 따라서 문자가 X일 때 스택에 넣고, .일 때 스택에서 있는 것들을 빼내서 출력하고 마지막에 .을 붙이는 방식으로 코드를 구현하였으나, 점이 없는 부분의 출력을 어떻게 구현하는지 몰라서 많이 고생하다가 좋지 않은 로직이라는 판단하에 다른 풀이 방법으로 변경하였다.

import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next(); // 사용자로부터 폴리오미노 문자열을 입력받음
        sc.close(); // 스캐너를 닫음

        String res = "";
        res = poliomino(s); // 폴리오미노 변환 함수 호출
        System.out.println(res); // 결과 출력
    }

    // 주어진 폴리오미노 문자열을 변환하는 함수
    private static String poliomino(String s) {
        Stack<Character> stack = new Stack<>(); // 스택 생성
        StringBuilder ansBuilder = new StringBuilder(); // 변환된 결과를 저장할 StringBuilder
        String A = "AAAA", B = "BB"; // 변환 규칙에 따른 문자열 상수 정의

        for (char c : s.toCharArray()) {
            if (c == 'X') {
                stack.push(c); // 'X' 문자일 경우 스택에 추가
            } else if (c == '.') {
                if (stack.size() % 2 != 0) {
                    return "-1"; // 스택에 남은 요소가 홀수면 변환 실패
                }

                while (!stack.isEmpty()) {
                    if (stack.size() >= 4) {
                        ansBuilder.append(A); // 'AAAA' 추가
                        stack.pop();
                        stack.pop();
                        stack.pop();
                        stack.pop();
                    } else {
                        ansBuilder.append(B); // 'BB' 추가
                        stack.pop();
                        stack.pop();
                    }
                }

                ansBuilder.append('.'); // '.' 추가
            }
        }

        return ansBuilder.toString(); // 최종 결과 반환
    }
}

입력: XX.XXXXXXXXXX..XXXXXXXX...XXXXXX
출력: BB.AAAAAAAABB..AAAAAAAA...

이런 식으로 마지막 부분이 출력되지 않는다.

 

정답 풀이

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next(); // 사용자로부터 폴리오미노 문자열을 입력받음
        sc.close(); // 스캐너를 닫음

        String answer = "";
        answer = poliomino(s); // 폴리오미노 변환 함수 호출
        System.out.println(answer); // 결과 출력
    }

    // 주어진 폴리오미노 문자열을 변환하는 함수
    private static String poliomino(String s) {
        String ans = ""; // 변환된 결과를 저장할 문자열
        String A = "AAAA", B = "BB"; // 변환 규칙에 따른 문자열 상수 정의

        // 문자열에서 "XXXX" 패턴을 "AAAA"로 대체하여 A를 채움
        s = s.replaceAll("XXXX", A);

        // 문자열에서 "XX" 패턴을 "BB"로 대체하여 B를 채움
        ans = s.replaceAll("XX", B);

        // 변환된 문자열에 'X' 문자가 남아있다면 폴리오미노 변환 실패
        if (ans.contains("X")) {
            ans = "-1"; // 결과를 -1로 설정
        }

        return ans; // 최종 결과 반환
    }
}

그리디 알고리즘에 대한 공부가 아직 부족하다는 것을 느꼈다. 

1. "XXXX" 패턴을 "AAAA"로 대체하고 "XX" 패턴을 "BB"로 대체하여 문자열을 변환
2. 변환된 문자열에 'X' 문자가 남아있다면, 폴리오미노 변환 실패로 -1을 반환

이런 순서로 문제풀이를 진행하였다.