[백준] 12904번 : A와 B – JAVA [자바]

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

 

 

---

문제

 

 

---

해결 방법

이 문제는 그리디 알고리즘(Greedy Algorithm)을 사용하여 해결할 수 있다. 왜냐하면 특정 상황에서 선택할 수 있는 연산이 항상 하나로 정해져 있기 때문이다. 일반적으로 문자열 S에서 T로 변환하는 방식으로 접근하면 여러 경우의 수를 고려해야 하지만, T에서 S로 변환하는 방식으로 접근하면 연산이 명확하게 결정된다. S에서 T로 변환하는 방법은 밑에 그림처럼 여러 경우의 수가 있다.

S에서 T로 가는 여러 경우의 수

 

하지만, 문자열 T의 마지막 문자가 'A'라면 그 이전 상태는 반드시 'A'를 추가하기 전의 상태이므로 'A'를 제거하면 된다. 반면 마지막 문자가 'B'라면 그 이전 상태는 반드시 문자열을 뒤집고 'B'를 추가하기 전의 상태이므로 'B'를 제거한 후 문자열을 뒤집으면 된다. 이러한 규칙에 따라 항상 유일한 최적의 선택이 존재하므로, 그리디 방식으로 해결할 수 있다.

그리디 방식을 적용한 S에서 T로 가능 경우

 

1. 문자열 T에서 시작하여, 마지막 문자가 A이면 이를 제거한다.

2. 문자열 T의 마지막 문자가 B이면 이를 제거한 후 문자열을 뒤집는다.

3. 위 과정을 반복하여 문자열 S가 나오면 변환이 가능하므로 1을 출력하고, S보다 길이가 짧아질 경우 변환이 불가능하므로 0을 출력한다.

 

---

코드 

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String start = br.readLine();
        String target = br.readLine();
        
        System.out.println(canTransform(start, target));
    }
    
    public static int canTransform(String start, String target) {
        // 문자열의 길이가 S보다 긴 동안 반복
        while (target.length() > start.length()) {
            // 마지막 문자 확인
            char lastChar = target.charAt(target.length() - 1);
            // 마지막 문자 제거
            target = target.substring(0, target.length() - 1);
            
            // 마지막 문자가 'B'였다면 문자열을 뒤집음
            if (lastChar == 'B') {
                target = new StringBuilder(target).reverse().toString();
            }
        }
        // 최종적으로 변환된 문자열이 S와 같은지 확인
        return start.equals(target) ? 1 : 0;
    }
}

 

 

---

코드 설명

 

1. while 문을 사용하여 target의 길이가 start보다 길 때까지 반복한다.

2. target의 마지막 문자를 확인하여:

- 'A'라면 그냥 제거한다.

- 'B'라면 제거한 후 문자열을 뒤집는다.

3. 최종적으로 target이 start와 같아지면 변환이 가능하므로 1을 출력하고, 아니라면 0을 출력한다.

 

---

시간 복잡도 분석

 

각 단계에서 문자열의 길이가 1씩 줄어들므로, 연산 횟수는 최대 O(N)이다. 문자열의 최대 길이가 1000이므로, O(N) 시간 복잡도로 충분히 해결할 수 있다.