BOJ-12904 A와 B

1. 문제

문제 링크 : https://www.acmicpc.net/problem/12904

알고리즘 분류 : 문자열, Greedy

2. 고민

해당 문제는 단순하게 아래 두 조건을 구현한

Brute Force 알고리즘으로 풀 수 있을 것이라고 생각했습니다.

문자열의 뒤에 A를 추가한다.

문자열을 뒤집고 뒤에 B를 추가한다.

3. 1차 시도 (실패)

    import java.io.*;

    public class Main {
        static String S, T;

        public static boolean isPossible(String str) {
            if(str.equals(T))   return true;
            if(str.length() > T.length())   return false;

            if(isPossible(str.concat("A")))  return true;
            if(isPossible(new StringBuilder(str).reverse().toString().concat("B"))) return true;

            return false;
        }

        public static void main(String[] args) throws IOException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

            S = br.readLine();
            T = br.readLine();

            System.out.println(isPossible(S) ? 1 : 0);
        }
    }

결과는 TLE였습니다….

이유는 Brute Force 알고리즘을 통해 구현한다면

시간복잡도는 O(2^n)이고, 문자열 길이는 1000이기 때문에

TLE가 뜨는 것이 당연했습니다.

생각을 좀 더 해보니 끝자리 문자가 무엇이냐에 따라 두 조건 중 하나의 조건만 택할 수 있었습니다.

예를 들면, 끝자리가 A인 경우 아무리 방법을 써도

“문자열을 뒤집고 뒤에 B를 추가한다.”의 조건은 사용할 수 없는 것이죠.

해당 방법으로 다시 구현했더니 AC가 나왔습니다.

4. 2차 시도 (성공)

    import java.io.*;

    public class Main {
        static String S, T;

        public static boolean isPossible(String str) {
            if(str.length() == S.length())  return str.equals(S);

            if(str.charAt(str.length()-1) == 'A')   return isPossible(str.substring(0, str.length()-1));
            else return isPossible(new StringBuilder(str.substring(0, str.length()-1)).reverse().toString());
        }

        public static void main(String[] args) throws IOException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

            S = br.readLine();
            T = br.readLine();

            System.out.println(isPossible(T) ? 1 : 0);
        }
    }

이 후, 다른 분들이 해결하신 코드를 보았습니다.

제가 사용한 방법은 문자열을 직접 뒤집으면서 비교하는 방법이지만,

다른 분들은 시작점과 끝점을 초기화하고

해당 문자열이 뒤집어진 문자열인지 아닌지를 구별하는 isReverse 변수를 두셨습니다.

“문자열의 뒤에 A를 추가한다.” 조건인 경우, end를 하나씩 줄이고

“문자열을 뒤집고 뒤에 B를 추가한다.” 조건인 경우,

start를 하나씩 늘리면서 isReverse를 반대 값으로 변경해주는 방법으로 해결하셨습니다.

그래서 해당 방법으로도 풀어보았더니 더 효율적인 코드가 되었습니다.

5. 3차 시도 (성공)

    import java.io.*;

    public class Main {
        public static void main(String[] args) throws IOException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            String S, T;
            boolean isReverse = false;

            S = br.readLine();
            T = br.readLine();
            int start = 0;
            int end = T.length()-1;

            while(S.length() < end - start + 1) {
                int idx = isReverse ? start++ : end--;
                if(T.charAt(idx) == 'B')    isReverse = !isReverse;
            }

            String test = T.substring(start, end+1);
            if(isReverse)   test = new StringBuilder(test).reverse().toString();
            System.out.println(test.equals(S) ? 1 : 0);
        }
    }

            
              📕 개인 기록용 블로그입니다.
              😊 오타나 잘못된 정보가 있을 경우 댓글이나 메일로 말씀해주시면 바로 수정하겠습니다! 😊