백준 1343번: 폴리오미노 (Python/Java)

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

1343번: 폴리오미노

 

 

 

접근

---

이 문제 또한 기본적인 형태의 그리디 알고리즘 문제였다.

 

해당 문제에서 주의깊게 살펴봐야 할 조건은 '사전 순으로 가장 앞서는 답'이다. 사전 순으로 가장 앞선다는 이야기는 AAAA와 BB 둘 다 동시에 들어갈 수 있을 때, AAAA가 들어가는 것을 출력해야 한다는 뜻이다. 즉, 해당 문제에서 답을 구하기 위해 해야하는 최선의 선택은 'BB보다 AAAA가 먼저 나오는 조합'이다.

 

우선 입력된 문자열을 for문으로 돌려, '.'이 나올 때까지의 문자 수를 구했다. 예를 들어 예제 3번처럼 'XXXX....XXX.....XX'의 경우 첫번째 '.'이 나오기 전까지 'X'는 총 4번이 나온다. 그렇다면 이 4를 기준으로 'AAAA'와 'BB'가 들어갈 수 있는 횟수를 구한다. 'AAAA'의 경우 4개의 문자열이기 때문에 4로 나눠어 떨어지면 들어갈 수 있다. 나누어 떨어지지 않는다면? 나머지를 다시 2로 나눠보면 'AAAA'로 채워넣지 못한 빈 칸을 'BB'로 채울 수 있는지 확인할 수 있다. 이 방법으로 문자열의 마지막까지 반복하면 반절 해결이다.

 

위의 방법으로는 '.'이 나올 때까지 for문을 돌려 'X'가 몇번 나왔는지 확인하는 것이기 때문에 만약 입력값에 '.'이 없다면 빈 값을 출력하게 될 것이다. 때문에 for문의 마지막에 따로 다시 'X'의 개수를 확인하고, 채워넣는 절차가 필요하다. 이 부분까지 감안해 코드를 작성하면 문제 해결이다.

 

 

 

풀이

---

Python

sentence = input()

result = ""
round = 0
for i in range(len(sentence)):

    if sentence[i] == "X":
        round += 1

        if i == (len(sentence)-1):
            if (round%4)%2 == 0:
                result += "A"*(round//4)*4
                result += "B"*(round%4)
            else:
                result = -1
                break

    elif (sentence[i] == ".") or (i == (len(sentence)-1)):
        
        if (round%4)%2 == 0:
            result += "A"*(round//4)*4
            result += "B"*(round%4)
        else:
            result = -1
            break

        round = 0
        result += "."

print(result)

 

Java

import java.util.Scanner;

public class Main {
    
    public static void main(String[] args) {
        
        Scanner scan = new Scanner(System.in);
        String[] sentence = (scan.nextLine()).split("");

        String result = "";
        int round = 0;
        for(int i = 0 ; i < sentence.length ; i++){

            if(sentence[i].equals("X")){
                round++;

                if(i == (sentence.length-1)){
                    if((round%4)%2 == 0){
                        result += "A".repeat((round/4)*4);
                        result += "B".repeat(round%4);
                    }else{
                        result = "-1";
                        break;
                    }
                }
            }else if(sentence[i].equals(".") || (i == (sentence.length-1))){
                if((round%4)%2 == 0){
                    result += "A".repeat((round/4)*4);
                    result += "B".repeat(round%4);
                }else{
                    result = "-1";
                    break;
                }

                round = 0;
                result += ".";
            }
        }

        System.out.println(result);

    }
}

 

 

 

후기

---

이번 문제 역시 쉽게 풀 수 있는 간단한 그리디 알고리즘 문제였다. 이런 난이도 쉬운 문제를 풀 때엔 더 간결한 풀이방식이 있을 텐데 조금 난잡하게 푸는 것 같아 아쉬움이 든다. 쉬운 문제를 풀더라도 조금 더 간결하게 풀 수 있는 방법을 찾아봐야겠다.