백준 12904번: A와 B (Python/Java)

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

12904번: A와 B

 

 

 

접근

---

문제 조건을 잘 살펴보면 어렵지 않게 그 힌트를 얻을 수 있다. 한번 연산이 수행될 때마다 글자 맨 뒤에 A가 되었건, B가 되었건 글자가 붙는다. 이 얘기는 한번 연산이 수행될 때마다 무조건 글자 수가 늘어난다는 것이다. 그리고 한번 연산을 할 때마다 뒤에 A 혹은 B가 붙기 때문에 바로 직전에 어떤 연산을 통해 해당 글자가 출력되었는지 확인할 수 있다. 이제 이걸로 모든 힌트를 얻었다.

 

시작 단어에서부터 경우의 수를 체크하기 시작한다면 확인해야 할 연산이 너무 많아진다. 현실적으로 문제 풀이가 힘들어진다. 그렇다면 반대로 완성 단어에서 시작 단어로 가는 것은 어떨까? 우리는 단어의 맨 뒤에 있는 글자 A 혹은 B를 통해 어떤 연산으로 해당 글자가 나왔는지 확인할 수 있다. 이를 이용해 역으로 탐색하는 것이다. 어디까지 해야 할까? 우리는 무조건 뒤에 단어 하나를 붙인다는 연산의 조건을 통해 무조건 글자 수가 늘어난다는 것을 알 수 있다. 그렇다면 우리는 시작 단어와 완성 단어의 글자 수가 같아지는 순간까지 연산을 역으로 탐색하면 된다.

 

이렇게 완성 단어가 수행한 연산들을 역으로 수행해 나온 글자와 시작 글자가 같다면 시작 단어는 완성 단어가 될 수 있고, 만약 같지 않다면 시작 단어는 연산을 어떻게 수행하더라도 완성 단어가 될 수 없다.

 

 

 

풀이

---

Python

startWord = input()
goalWord = input()

while len(startWord) < len(goalWord):
    if len(startWord) < len(goalWord):
        if goalWord[len(goalWord)-1] == "A":
            subWord = ""
            for i in range(len(goalWord)-1):
                subWord += goalWord[i]
            goalWord = subWord
            
        else:
            subWord = ""
            for i in range(len(goalWord)-2, -1, -1):
                subWord += goalWord[i]
            goalWord = subWord

if startWord == goalWord:
    print(1)
else:
    print(0)

 

Java

import java.util.Arrays;
import java.util.Scanner;

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

        String[] startWord = (scan.nextLine()).split("");
        String[] goalWord = (scan.nextLine()).split("");

        while(startWord.length < goalWord.length){
            if(startWord.length < goalWord.length){
                if(goalWord[(goalWord.length-1)].equals("A")){
                    String[] subWord = new String[goalWord.length-1];
                    for(int i = 0 ; i < (goalWord.length-1) ; i++){
                        subWord[i] = goalWord[i];
                    }
                    goalWord = subWord;
                }else{
                    String[] subWord = new String[goalWord.length-1];
                    for(int i = (goalWord.length-2) ; i > -1 ; i--){
                        subWord[(goalWord.length-2) - i] = goalWord[i];
                    }
                    goalWord = subWord;
                }
            }
        }

        if(Arrays.equals(startWord, goalWord)){
            System.out.println(1);
        }else{
            System.out.println(0);
        }

    }

}

 

후기

---

문제를 푼 건 지금이지만 아주 예전, 알고리즘을 처음 풀어볼 때 이 문제를 한번 본 적이 있다. 그때는 그리디 알고리즘에 대한 개념만 대충 알고 있었기 때문에 잘 풀리지 않았었는데 이번에 제대로 읽어보니 세상 이렇게 쉬운 문제가 없었다. 역시 알고리즘의 개념만 제대로 파악하고 있다면 '읭?' 하고 생각했던 문제들도 쉽게 풀 수 있다고 생각했다.

 

추가로 파이썬에서 맨 뒤의 글자를 뺀 단어 혹은 거꾸로 뒤집은 단어는 굳이 저렇게 코드를 구성할 필요가 없다. 더욱 간단하게 구현할 수 있다. 예를 들어 'goalWord [::-1]'과 같이. 자바 또한 StringBuffer를 이용하면 쉽게 뒤집을 수 있는데, 처음 자바를 공부할 때 StringBuffer를 몰랐었고(아마 프로그래밍 언어가 처음인지라 기본적인 for문에 익숙해지는 것을 염두하고 굳이 이렇게 했던 걸로 기억한다.) 이게 그대로 습관이 되어 파이썬까지 넘어왔다. 언어에 대한 이해와 빠른 코드 작성을 위해 습관보다는 더 좋은 방법을 꾸준히 찾아 익숙해지도록 해야겠다. 오늘은 어쩐지 문제가 쉽게 풀리더니 결국은 또 이렇게 한번 반성하고 가는구나.