[백준] 12904 A와 B - JAVA

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

12904번: A와 B

 

 

[풀이]

• S → T 찾기(X) ,  T → S 찾기(O)
• 주어진 문자열 S에서 할 수 있는 방법은 A를 추가하거나, B를 추가하거나 (+뒤집기) 두개 다 가능하다. 
• 반대로 T에서 가능한 방법은 , 아래와 같이 가장 끝 문자가 무엇이냐에 따라 하나만 가능하다. 
  1. 가장 끝 단어가 'A' 일경우 : A 빼기 
  2. 가장 끝 단어가 'B' 일 경우: B 빼고 뒤집기 
• 따라서 S에서 T를 찾는 것보다 T에서 끝문자가 무엇이냐에 따라 연산하며 S를 찾는것이 더 효율적이다.

---

 

[구현 과정]

• DeleteLast() : 문자열의 가장 마지막 문자 제거하는 메소드 
• Reverse() : 문자열 뒤집는 메소드 

🌟T의 길이가 S의 길이보다 짧아질 수는 없다. (S에서 가능한 연산은 'A' 또는 'B'를 추가하는 것이므로) 

 

1. 두 문자열을 입력받아 s,t에 저장한다.

 

2. t의 길이가 s의 길이보다 길 동안만 아래의 과정을 반복한다. 

- t 문자열의 가장 끝 문자를 last 변수에 저장한다. (charAt 사용)
- last의 값에 따라 아래 두개의 경우 중 하나를 실행한다. 
     - last가 'A'일 경우 : t에서 가장 끝 문자를 제거한다. ▶DeleteLast() 
     - last가 'B'일 경우 : t에서 가장 끝 문자열을 제거한 후, 뒤집는다. ▶DeleteLast() > Reverse()
- 만약 t가 s와 동일하다면 1을 출력하고 프로그램을 종료한다. 

 

 

3. 위 반복문이 종료되었을 경우 (t의 길이가 s보다 짧아졌을 경우), 가능한 연산이 없으므로 0을 출력한다.

 

---

 

[소스 코드]

import java.io.*;

public class Main {
	static String t; 
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
		
		String s= br.readLine();
		t= br.readLine(); 
		
		while(t.length() > s.length()) {
			char last = t.charAt(t.length()-1); 
			//만약 A라면 , A를 빼는 거 밖에 방법이 없음 
			if(last== 'A') DeleteLast(); 
				
			//만약 B라면, B를 빼고 뒤집는 거 밖에 방법이 없음 
			else {
				DeleteLast();
				Reverse(); 
			}
			
			if(t.equals(s)) {
				System.out.println(1);
				return; 
			}
		}
		System.out.println(0);
	}//end of main
	
	//마지막 뒤에 한 단어 빼기 
	private static void DeleteLast() {
		t= t.substring(0, t.length()-1); 
	}
    
	//문자열 뒤집기
	private static void Reverse() {
		String rev =""; 
		for(int i=t.length()-1; i>=0; i--) {
			rev += t.charAt(i); 
		}
		t=rev;
	}
}//end of class