백준 12904번. A와B (Java)

1. 문제 조건

2. 아이디어

주어진 시간은 2초이다.

S의 길이는 최소 1에서 최대 999, T의 길이는 최대 1000이다. S에서 T가 만들어질 수 있는 지 확인하기 위해 문자열 뒤에 A을 한 번 추가해보고, 또 문자열을 뒤집고 B를 추가하는 연산을 각각 수행해보는 완전탐색 방식은 시간초과가 난다. 

S의 길이가 1이고 T의 길이가 1000인 최악의 상황을 고려했을 때, 999자리만큼 문자를 늘려야한다. 위에서 설명한 방식은 한 자리씩 늘릴 때마다 2가지 경우의 수가 존재하므로 2의 999제곱이 되어 시간초과가 발생한다. 따라서 S에서 완전탐색으로 T를 만들어나가는 과정은 적용할 수 없다.

 

그렇다면 반대로 T에서 S를 만들어나가면 된다.

S에 1번 연산을 적용하면 맨 뒤 알파벳은 A가 되고 2번 연산을 적용하면 맨 뒤 알파벳이 B가 된다. 따라서 T는 맨 뒤 알파벳만 보고 1번과 2번중 어떤 연산이 적용된 결과인 지 알 수 있으니, 한 번만 역연산을 취하면 된다.

 

따라서 역연산을 S와 T의 길이가 같지 않을 때까지 반복한 후, 길이가 같아지는 순간 두 문자열이 동일한지 확인하면 S를 T로 만들 수 있는지의 여부를 알아낼 수 있다. 

 

 

 

3. 구현

우선 StringBuffer를 사용해서 문자열을 뒤집는 방식을 택해 구현했다.

package gold5;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.stream.Stream;

public class Main_12905a와b {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    static String S, T;

    public static void main(String[] args) throws IOException {
        input();
        System.out.println(pro(S, T));
    }

    public static int pro(String original, String target) {

        while (original.length()<target.length()) {
            //문자열 맨 뒤가 A이면 A 떼기
            if (target.charAt(target.length() - 1) == 'A') {

                target = target.substring(0, target.length() - 1);
            } else {
                //문자열 맨 뒤가 B면 떼고 뒤집기
                target = target.substring(0, target.length() - 1);
                target = reverse(target);
            }

        }
        if(target.equals(original)) return 1;
        else return 0;
    }

    public static String reverse(String str) {
        StringBuffer sb = new StringBuffer(str);
        return sb.reverse().toString();
    }


    public static void input() throws IOException {
        S = br.readLine();
        T = br.readLine();
    }
}

 

문제 풀이 이후 다른 사람들의 풀이를 살펴보니 StringBuilder를 이용해 아래와 같이 문자열을 뒤집는 방식도 있다는 것을 알았다. 이 방법을 적용하면 맨 뒤 알파벳을 지우는 것도, 문자열을 뒤집는 것도 훨씬 간편하게 구현이 가능했다. 다음에 문자열 뒤집는 풀이가 필요할 때 적용해봐야겠다!

    public static int pro(String original, String target) {
        
        StringBuilder t = new StringBuilder(target);
        while (original.length()<t.length()) {
            //문자열 맨 뒤가 A이면 A 떼기
            if (t.charAt(t.length() - 1) == 'A') {

                t.deleteCharAt(t.length()-1);
            } else {
                //문자열 맨 뒤가 B면 떼고 뒤집기
                t.deleteCharAt(t.length()-1);
                t.reverse();
            }

        }
        if(t.toString().equals(original)) return 1;
        else return 0;
    }