(백준 12904번) A와 B

https://www.acmicpc.net/problem/12904

12904번: A와 B

#문제 

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

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

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

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

 

#알고리즘 

그리디,문자열,구현

 

#나의 풀이 방법

문제 자체는 되게 심플했다.

문자열은 A와 B밖에 없고..  그저 S의 문자열에 2가지 연산만 적용하여 T와 같은지 확인하여

확인하면 1 안되면 0을 출력하는 문제이다...

처음 이 문제를 풀 때는 백트래킹과 브루트포스로도 가능할 것 같아서 2가지 연산을 dfs로 적용했더니

역시나 그리디 문제라서 시간초과가 났다...

S를 T로 만들기까지 확인 하는 과정에서 어떻게 하면 그리디적으로 구현을 할까 생각하다가 도무지 생각이 나질 않았다.

구글링해서 다른 블로그를 참고해보니 역순이라는 단어가 눈에 띄어 바로 그 블로그를 닫고 역순으로 생각해보았다.

 

예를 들어

 

S가 B

T가 ABBA라 한다면,

 

S를 확인하는 것이 아닌 T를 맨끝에서부터 체크하여 S가 될때까지 연산을 반대로 적용한다. (S랑 길이가 같을때까지)

 

연산 1이 A를 추가해주는 것이므로, 반대로 A를 제거해주는 연산으로 만들고

연산 2가 문자열을 뒤집고 B를 추가해준 것이라면, 반대로 B를 제거하고 문자열을 뒤집는다.

 

T의 맨 마지막 글자가 A라면 연산 1을 적용, B라면 연산 2를 적용하여 S와 길이가 같을때까지 반복한 후,

S와 T가 같은지만 확인해주면 된다

 

#나의 코드

import java.util.*;
//1t

public class Main {
	
	public static String change1(String s) {
		s = s.substring(0,s.length()-1);//A 제거
		return s;
	}
	
	public static String change2(String s) {
		
		s = s.substring(0,s.length()-1);//B제거후,
		
		StringBuffer sb = new StringBuffer(s);
		s = sb.reverse().toString();//뒤집기
		
		return s;
	}
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		String S = sc.next();
		String T = sc.next();
		

		while(S.length() < T.length()) {
			
			if(T.charAt(T.length()-1) == 'A') {
				T = change1(T);
			}
			else {
				T = change2(T);
			}
		}
		
		if(S.equals(T))
			System.out.println(1);
		else
			System.out.println(0);
		
	}

}

.

그리디 문제는 무조건 FM대로 복잡하게 고민하는 것뿐만이 아닌 상황에 따라서 역으로도 생각해보는 유동적인 문제 해결 과정이 필요하다는 것을 깨닫게 된 것 같다.