[백준/Java] 12904번 - A와 B

문제 & 난이도

 

• 그리디 알고리즘
• 난이도 : 골드 5

 

풀이

package greedy;

import java.util.Scanner;

public class Beakjoon12904 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //첫째 줄 - 문자열 S
        String S = sc.nextLine();

        //둘째 줄 - 문자열 T
        String T = sc.nextLine();

        //T→S
        while(T.length() > S.length()) {
            //T의 맨 마지막 문자가 A로 끝나면 A 제거
            if(T.charAt(T.length()-1)=='A'){
                //substring메서드 이용하여 특정 부분만 추출
                T = T.substring(0, T.length()-1);
            }
            //T의 맨 마지막 문자가 B로 끝날 경우
            else{
                //B제거
                T = T.substring(0, T.length()-1);
                //문자열 뒤집는 메서드 reverse를 가지고있는 클래스 StringBuilder 인스턴스 생성
                StringBuilder sb = new StringBuilder(T);
                //toString()전 T의 자료형은 StrungBuilder이다. 후에 있을 문자열 비교를 위해 toString을 사용하여 문자열 자료형으로 변경.
                T = sb.reverse().toString();
            }
        }

        //결과 비교
        if(S.equals(T)){
            System.out.println("1");
        }
        else{
            System.out.println("0");
        }


    }
}

 

결과 문자열 T의 마지막 문자가 A일 경우 옵션 1을 선택한 것이고, 마지막 문자가 B인 경우 옵션 2가 선택된 결과이다.

미래를 예측하지 않고 현재 상황에서의 마지막 문자만 보며 결과를 추리할 수 있는 그리디 문제. 

 

알게 된 것 & 느낀 점

 

처음, 문제를 S → T로 바꾸는 과정에 집중하였더니, 고려해야 할 사항이 너무 많아져서 다른 분의 풀이를 찾아봤다.

만약 내가 선택한 풀이법에서 해결이 안 된다면 끝까지 풀어보려 애쓰기보단 다른 방향으로의 풀이가 있는지 고민할 것!

 

*substring(int a, int b) : 문자열의 길이를 인덱스a부터 인텍스 b까지로 잘라줌.

*reverse() :  문자열을 뒤집어주는 메서드로, StringBuilder 클래스에 구현되어 있다.