[백준] 알고리즘 분류(그리디 알고리즘,JAVA)12904번, A와 B

문제 링크

12904번: A와 B

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 문자열을 바꾸는 연산은 문제에서 주어지는 2가지 연산만 사용이 가능합니다.

2. 연산을 이용해서 S를 T로 바꿀수 있는지 확인한 결과를 출력합니다.

3. 영어 단어는 'A'와 'B'로만 구성됩니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 단어 T 마지막 글자를 줄여가며 S를 만들 수 있는지 탐색합니다.

 

3. 만들 수 있으면 1, 만들지 못하면 0을 결과로 출력합니다.

 

 

T → S만들기.

 

T를 S로 만들 때에는 연산을 반대로 진행되도록 하면 됩니다.

 

현재 단어 T의 마지막 글자가 'A'일 때

 

연산 1 반대로 진행

 

= 마지막 글자 'A'를 지운다.

 

현재 단어 T의 마지막 글자가 'B'일 때

 

연산 2 반대로 진행

 

= 마지막 글자 'B'를 지운 뒤, 문자열 뒤짚기

 

예를 들어.

 

S  = "A"

T = "ABA"일 때

 

T의 마지막 글자 : 'A'

 

연산 1 반대로 진행!

 

'A' 제거

 

T = "AB"

 

T의 마지막 글자 : 'B'

 

연산 2 반대로 진행!

 

'B' 제거

 

T = "A"

 

단어 T 거꾸로 뒤짚기

 

T = "A"

 

S("A") == T("A")

 

S → T 가능!

 

예제입력 2.

1. 입력된 정보를 저장합니다.

S = AB

T = ABB

 

2. 단어 T 마지막 글자를 줄여가며 S를 만들 수 있는지 탐색합니다.

 

T의 마지막 글자 : 'B'

 

연산 2 반대로 진행!

 

'B' 제거

 

T = "AB"

 

단어 T 거꾸로 뒤짚기

 

T = "BA"

 

S("AB") != T("BA")

 

S → T 불가능!

 

3. 만들 수 있으면 1, 만들지 못하면 0을 결과로 출력합니다.

 

S("AB") != T("BA")

 

0을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• 단어 T의 마지막 글자에 따른 연산 1과 연산 2를 반대로 진행하여 S의 형태로 만들기를 진행합니다.
• T를 S의 형태로 만들었을 때 같으면 1, 다르면 0를 결과로 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

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

public class Main{
    static String S,T;
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //S, T 값 저장
        S = br.readLine();
        T = br.readLine();
        int size = T.length()-1;
        //T → S로 변경하기!
        for(int i=size;i>=S.length();i--){
            char c = T.charAt(i);
            T = T.substring(0, i);	//마지막 글자 제거하기
            if(c == 'B') {	//마지막 글자 'B'일 때 단어 T 뒤짚기
                StringBuilder temp = new StringBuilder();
                //뒤짚기 진행
                for (int j = i-1; j>=0;j--)
                    temp.append(T.charAt(j));
                T = temp.toString();
            }
        }
        //S == T가 같은지 확인
        if(S.equals(T))		//S → T 가능!
            bw.write("1");
        else		//S → T 불가능!
            bw.write("0");
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
}