백준 12904 A와 B c++, Kotlin (투 포인터)

문제 출처 : https://www.acmicpc.net/problem/12904

12904번: 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을 출력한다.

알고리즘 분류

• 구현
• 문자열
• 그리디 알고리즘

풀이

투 포인터로 풀었지만 사실 문자열의 요소를 제거해가면서 그리디하게 풀어도 된다.

핵심 풀이는, S를 T로 만드는 게 아니라 T를 S로 만드는 것이고, 다음과 같은 과정을 반복해서 만들 수 있다.

1. T의 마지막 요소가 B라면 B를 제거한 뒤 T를 뒤집는다.

2. T의 마지막 요소가 A라면 A를 제거한다. 

3. T의 길이와 S의 길이가 같아질 때까지 1,2과정을 반복한다.

4. T와 S의 길이가 같다면 두 문자열을 비교하여 정답을 출력한다.

 

위의 풀이에서 문자열을 제거하는 대신, 투 포인터를 이용하는 방법은 다음과 같다.

start, end 포인터를 두고, end의 요소가 B라면 end를 왼쪽으로 한 칸 이동시키고,

뒤집혔으니 end대신 start의 요소를 검사한다. 이를 end-start의 길이가 S의 길이와 같아질 때까지 반복한다.

효율성은 투 포인터가 더 좋다.

c++풀이는 문자열에 pop_back()을 사용할 수 있어서 문자열을 지우는 식으로 했으나 굳이굳이 투 포인터도 사용해봤다.

Kotlin풀이는 순수 투 포인터 풀이이다.

코드(c++)

#include <iostream>
#include <string>

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	string s, t;
	cin >> s >> t;

	int answer = 1;
	bool isReverse = false;

	while (s.length() != t.length()) {
		int sP = 0;
		int eP = t.length() - 1;
		if (isReverse) {
			if (t[sP] == 'B') 
				isReverse = false;
			t.erase(t.begin());
		}
		else {
			if (t[eP] == 'B')
				isReverse = true;
			t.pop_back();
			
		}
	}
	if (isReverse) {
		for (int i = s.length()-1; i >= 0; i--) {
			if (t[i] != s[s.length() - i - 1]) {
				answer = 0;
				break;
			}
		}
	}
	else {
		for (int i = 0; i < t.length(); i++) {
			if (t[i] != s[i]) {
				answer = 0;
				break;
			}
		}
	}
	cout << answer;
}

코드(Kotlin)

fun main() = with(System.out.bufferedWriter()){
    val br = System.`in`.bufferedReader()
       val S = br.readLine()
    val T = br.readLine()
    var isReverse =false
    var s=0
    var e=T.length-1
    while(e-s+1!=S.length){
        if(isReverse){
            if(T[s]=='B'){
                isReverse=false
            }
            s++
        }
        else{
            if(T[e]=='B'){
                isReverse=true
            }
            e--
        }
    }
    if(isReverse){
        for(i in 0 until S.length){
            if(S[i]!=T[e-i]){
                write("0")
                close()
                return
            }
        }
    }
    else{
        for(i in 0 until S.length){
            if(S[i]!=T[s+i]){
                write("0")
                close()
                return
            }
        }
    }
    write("1")
    close()
}