알고리즘 풀이 - 백준 12904(A와 B, 그리디(Greedy))

 

관련글

 

그리디 알고리즘 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

A와 B로만 이루어진 영단어가 있을 때, 영단어 S를 T로 바꿀 수 있는 지 없는 지 구하는 문제

 

 

2. 풀이

 

영단어 T를 다시 S로 만들 수 있는지를 체크하면 문제를 해결할 수 있다.

 

우선, 영단어 T를 분해하여 각 문자를 Deque 자료구조에 넣어 양 방향에서 뺄 수 있도록 구현한다.

그리고 현재 가장 마지막에 추가된 문자가 어느 위치인지를 체크할 수 있도록 별도의 변수를 만든다. 이를 통해 T → S로 변환하기 위해 어떤 문자를 제외해야 할지를 알 수 있다.

 

예를 들어, back=1이면, 다음에 뺄 문자는 앞쪽에 있다는 의미이며, back=-1이면 다음에 뺄 문자는 뒤쪽에 있다는 의미이다.(처음에는 -1로 지정한다.)

 

그래서, 다음에 뺄 문자가 A라면, 해당 문자를 빼고 끝이지만 B라면 뺀 뒤 back에 -1을 곱해 다음 뺄 문자의 위치를 업데이트 해주어야 한다.

 

이 과정을 반복하여 S의 길이와 T를 분해한 Deque의 크기가 동일한 경우, Deque에서 각 문자를 연결하여 만든 하나의 문자열이 S와 동일한 경우 1을, 아닌 경우 0을 출력한다.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

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 s = br.readLine();
        String t = br.readLine();
        
        // t의 모든 문자 하나하나를 Deque에 넣는다.
        Deque<Character> dq = new LinkedList<>();
        for(int i=0; i < t.length(); i++){
            dq.offerLast(t.charAt(i));
        }
        
        // 문자열의 앞과 뒤를 설정한다.
        // 1이면 Deque의 앞에서 시작한다는 의미이며, -1이면 뒤에서 시작한다는 의미이다.
        int back = -1;  // 문자열 끝 위치
        while(true){
            // 문자를 뒤에서 부터 뺀다.
            char c = ' ';
            if(back == -1) c = dq.pollLast();
            else c = dq.pollFirst();
            
            // 뺀 문자가 B이면 뒤집어야 하므로 back을 바꾸어준다.
            if(c == 'B'){
                back *= -1;
            }
            
            // 만약 t에서 문자를 제외한 결과와 s의 길이가 같아졌다면
            // 방향에 따라 문자를 연결하여 일치 시 1을 출력하고 아니면 0을 출력한다.
            if(s.length() == dq.size()){
                String temp = "";
                while(!dq.isEmpty()){
                   if(back == 1){
                       temp += dq.pollLast();
                   } else {
                       temp += dq.pollFirst();
                   }
                }
                if(temp.equals(s)){
                   System.out.println(1);
                   return;
                } else {
                   System.out.println(0);
                   return;
                }
            }
        }
    }
}

 

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.