[Baekjoon] A와 B

👀 문제 설명

문제

수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다.

이런 사실에 놀란 수빈이는 간단한 게임을 만들기로 했다. 두 문자열 S와 T가 주어졌을 때, S를 T로 바꾸는 게임이다. 문자열을 바꿀 때는 다음과 같은 두 가지 연산만 가능하다.

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

주어진 조건을 이용해서 S를 T로 만들 수 있는지 없는지 알아내는 프로그램을 작성하시오. 

 

입력

첫째 줄에 S가 둘째 줄에 T가 주어진다. (1 ≤ S의 길이 ≤ 999, 2 ≤ T의 길이 ≤ 1000, S의 길이 < T의 길이)

 

출력

S를 T로 바꿀 수 있으면 1을 없으면 0을 출력한다.

 

예제 입력 1

B

ABBA

 

예제 출력 1

1

 

예제 입력 2

AB

ABB

 

예제 출력 2

0

 

✍🏻풀이

[틀린 풀이]

큐를 사용해서 S에서 연산을 해 새로운 문자열을 만들고, 그걸 다시 큐에 넣는다. (연산한 S의 길이가 T의 길이보다 작거나 같을 동안만) 큐가 빌 때까지 연산을 하면서 만약 큐에 T와 같은 값이 들어가있다면 1을 출력한다.

-> 이렇게 하니까 메모리 초과가 났다. 같은 문자열이 큐에 들어가는 경우일거라고 생각해서 큐 대신 벡터를 사용하고, 연산한 S가 벡터 안에 있는지 확인한후, 벡터에 없을 때만 넣었다.

-> 이렇게 하니까 시간 초과 발생!

 

[정답]

S에서 T로 가는 연산을 수행하면 시간 초과가 난다!!

그래서 T에서 S로 가는 연산을 수행하고, T의 길이와 S의 길이가 같아졌을 때, 두 값을 비교해 같으면 1을, 다르면 0을 출력하면 된다!

 

코드

[C++]

//  A와 B (https://www.acmicpc.net/problem/12904)

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(NULL); cout.tie(NULL);

    string S, T;
    cin >> S >> T;

    // solve
    /**
     * 1. 먼저 T의 가장 끝 char를 확인한다.
     * 2-1. A라면 T의 가장 끝 char를 뺀다.
     * 2-2. B라면 T의 가장 끝 char를 빼고 문자열을 뒤집는다.
     */
    while (true) {
        if (T.length() == S.length()) {
            if (T == S) { // S를 T로 만들 수 있다.
                cout << "1\n";
            }
            else {
                cout << "0\n";
            }
            return 0;
        }

        if (T.length() < S.length()) {
            cout << "0\n";
            return 0;
        }

        // 아직 T의 길이가 S의 길이보다 크면
        string newStr = "";
        if (T[T.length() - 1] == 'A') { // 2-1
            newStr = T.substr(0, T.length() - 1);
        }
        else { // 2-2
            newStr = T.substr(0, T.length() - 1);
            reverse(newStr.begin(), newStr.end());
        }
        T = newStr;
    }

    return 0;
}

 

[JAVA]

 

package JAVA.Baekjoon.Simulation;

import java.io.*;
import java.util.*;

class BOJ_12904 {

    public static void main(String[] args) throws IOException {
        // input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuffer S = new StringBuffer(br.readLine());
        StringBuffer T = new StringBuffer(br.readLine());

        // !! JAVA에서 String은 변하지 않는 값이고, StringBuffer는 변할 수 있는 값이다 !!
        // solve
        /**
         * 1. 먼저 T의 가장 끝 char를 확인한다.
         * 2-1. A라면 T의 가장 끝 char를 뺀다.
         * 2-2. B라면 T의 가장 끝 char를 빼고, 문자열을 뒤집는다.
         */
        while (true) {
            if (T.length() == S.length()) {
                // StringBuffer의 equals는 메모리 주소와 값이 모두 같아야 true를 반환하고,
                // String의 equals는 메모리 주소가 달라도 값이 같으면 true를 반환하기 때문에
                // 비교를 위해선 String으로 바꾼 후에 비교한다!
                if ((T.toString()).equals(S.toString())) { // JAVA에서는 String 값을 비교하기 위해선 equals를 사용한다!!
                    System.out.println(1);
                    return;
                }
                else {
                    System.out.println(0);
                    return;
                }
            }

            if (T.length() < S.length()) {
                System.out.println(0);
                return;
            }

            // 아직 T의 길이가 S의 길이보다 크면
            if (T.charAt(T.length() - 1) == 'A') { // JAVA에서는 charAt을 사용해서 String의 특정 index의 char값을 가져온다.
                T.deleteCharAt(T.length() - 1); // T.length() - 1 위치에 있는 값을 지운다!
            }
            else {
                T.deleteCharAt(T.length() - 1);
                T.reverse(); // reverse()를 사용하면 간단하게 문자열을 뒤집을 수 있다.
            }
        }
    }
}