백준 12919 A와 B 2 c++ (투 포인터) 2022-06-20 코틀린 추가

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

12919번: A와 B 2

문제

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

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

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

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

입력

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

출력

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

알고리즘 분류

• 구현
• 문자열
• 브루트포스 알고리즘
• 재귀

풀이

비슷한 문제 : 2021.08.28 - [알고리즘 문제 풀이/백준] - 백준 12904 A와 B c++, Kotlin (투 포인터)

이런 부류의 문제는 차근차근 천천히 생각하면 어렵지 않다.

우선 S를 T로 만들 수 있는지 찾는 문제인데,

S를 T로 만들려면, T길이가 될 때까지 매번 1,2번 연산을 모두 시행해야 한다.

하지만 우리는 S를 T로 만들 수 있는지만 확인하면 되므로, 역으로 T가 S가 될 수 있는지만 확인하면 된다.

 

주어진 연산을 보면

문자열 T가 

~~A형태일 땐 1번 연산을 할 수 있고,

B~~B형태일 땐 2번 연산을 할 수 있고,

B~~A형태일 땐, 1,2번 연산을 모두 할 수 있고,

A~~B형태일 땐 아무 연산을 할 수 없다.

 

위의 규칙으로 주어진 T를 S의 길이까지 삭제해가면서 S와 같은지 확인할 수 있지만,

문자열의 삭제 연산은 효율적이지 않기 때문에, 두 개의 포인터를 두고 인덱스만 늘리거나 줄여나가면 된다.

우리가 연산을 할 때 확인해야 할 문자는 T의 맨 앞 문자와 맨 뒤 문자이기 때문에,

sP=0, eP =T.length()-1을 두면 시작 문자와 끝 문자를 찾을 수 있다.

만약 2번 연산을 해서 문자열이 뒤집힌 상태면,

sP가 있는 곳이 끝 문자가 될 것이고, eP가 있는 곳이 첫 문자가 될 것이다.

 

2022.06.20 kotlin 풀이

    if(t[e]=='A'){
        t.deleteCharAt(t.lastIndex)
        convertTToS(s,t)
        t.append('A')
    }
    if(t[0]=='B'){
        t.reverse()
        t.deleteCharAt(e)
        convertTToS(s,t)
        t.append('B')
        t.reverse()
    }

위 코드가 핵심이다.

그냥 끝 부분이 A이면 1번 연산해 보고 되돌리고,

첫 부분이 B면 2번 연산해 보고 되돌리면 된다.

 

코드1(c++)

#include <iostream>
#include <string>
using namespace std;

bool result;

void solve(string s, string t, int sP, int eP,bool isReverse) {
	if (s.length() == eP-sP+1) {
		bool isFinish = true;
		
		
		for (int i = 0; i < s.length(); i++) {
			if (isReverse) {
				if (s[i] != t[eP--]) {
					isFinish = false;
					break;
				}
			}
			else {
				if (s[i] != t[sP++]) {
					isFinish = false;
					break;
				}
			}
		}
		if (isFinish) result = true;
		return;
	}
	if (isReverse) {
		//뒤집혀있으면 e가 처음
		if (t[eP] == 'B') {
			solve(s, t, sP, eP-1, !isReverse);
		}
		//뒤집혀있으면 s가 끝
		if (t[sP] == 'A') {
			solve(s, t, sP+1, eP, isReverse);
		}
	}
	else {
		if (t[sP] == 'B') {
			solve(s, t, sP+1, eP, !isReverse);
		}
		if (t[eP] == 'A') {
			solve(s, t, sP, eP-1, isReverse);
		}
	}

}


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


	int sP = 0;
	int eP = t.length() - 1;

	solve(s, t, sP, eP,false);
	cout << result;
	return 0;
}

코드2(Kotlin)

import java.util.*
val br = System.`in`.bufferedReader()
var answer = 0
fun convertTToS(s: String, t: StringBuilder){
    if(s.length == t.length){
        if(s==t.toString()){
            answer=1
        }
        return
    }
    val e = t.lastIndex

    if(t[e]=='A'){
        t.deleteCharAt(t.lastIndex)
        convertTToS(s,t)
        t.append('A')
    }
    if(t[0]=='B'){
        t.reverse()
        t.deleteCharAt(e)
        convertTToS(s,t)
        t.append('B')
        t.reverse()
    }
}

fun main() = with(System.out.bufferedWriter()){
    //input
    val s = br.readLine()
    val t = StringBuilder(br.readLine())
    //solve
    convertTToS(s,t)
    //output
    write("$answer")
    close()
}