<java> 백준 12904 - 그리디

최근 백준 문제를 열심히 풀고 있긴 했었는데 최단시간계산이나 다익스트라 같은 난이도는 높지만 해결 방식만 알면 사용만으로 풀 수 있는 문제들로만 점수를 올리고 있어 점수를 물로 올리고 있는 것 같은 느낌이 들었다.

그래서 알고리즘 공부라는 본질적인 목표를 잃지 않도록 그리디 문제를 한동안 풀기로 했다.

이전 처럼 수월하게 풀리지는 않지만 하고 나면 확실히 머리를 썼다라는 기분이 들었다.

 

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

12904번: A와 B

문제는 해당 링크에서 확인 할 수 있다.

 

간단히 설명하자면 A,B를 규칙에 따라 추가 할 수 있다. 처음 주어진 단어에서 규칙에 맞게 추가해서 다음 단어를 완성 할 수 있는가였다.

 

처음 든 생각은 규칙이 있는가 찾아보기였다. 하지만 너무 복잡하고 BFS 밖에 떠오르지 않아 이 방식은 아닌 것 같다는 결론을 내렸다. 최근 몇 문제를 풀어보며 bfs 방식밖에 떠올리지 못하는 자신을 보며 너무 최근에 그러한 문제들만 풀었다는 생각을 하게되었다.

두번째는 단순하게 모든 경우의 수를 다 해보기 였다. A,B의 개수를 파악하여 각자를 개수에 맞게 넣을 수는 있었지만 이 방식은 시간 복잡도에서 이미 아웃이라고 생각하여 시간을 줄이는 것 보다 알고리즘이 진행되며 나오는 결과를 확인하여 아이디어를 얻고자 함이였다.

머리로 찬찬히 생각해보는것도 좋은 방식이긴 하지만 실제로 프로그램에게 시켜 결과의 변화를 지켜 보는 것도 때론 해결 책을 떠올리는데 좋은 힌트가 되기도 했기 때문이다.

set을 이용해 중복만 제거 한 정도에서 모든 수행을 하고 결과 값 중 해당 값이 있는지를 확인하여 결과를 도출하였는데 정답은 맞지만 당연하게도 시간 초과가 떴다.

그래서 마지막으로 결과 값에서 천천히 뒤의 값들을 삭제하는 방식을 사용하기로 했다. 여기서도 좀 더 복잡하게 생각하려 하면서 B가 뒤에 있을때 방향성을 줘서 앞부터 지워나가는 방식을 사용해 보려고 했으나 식이 점점 복잡해져 내 머리로 한번에 생각이 되지 않길래 그냥 글자 자체를 돌려버리는 방식을 사용하여 해결하였다.

StringBuilder.reverse() 라는 방식을 이번에 처음 알게 되었다.

StringBuilder 주요 메소드

• .append(): 문자열을 추가한다.
• .insert(int offset, String str): offset 위치에 str을 추가한다. 
• .replace(): 첫번째와 두번째 파라미터로 받는 숫자 인덱스에 위치한 문자열을 대체한다.
• .deleteCharAt(int index): 인덱스에 위치한 문자 하나를 삭제한다.
• .delete(int start, int end): start 부터 end-1 까지의 문자를 삭제한다. 
• .toString(): String으로 변환한다. 
• .reverse(): 해당 문자 전체를 뒤집는다. 
• .setCharAt(int index, String s): index 위치의 문자를 s로 변경
• .setLength(int len): 문자열 길이 조정, 현재 문자열보다 길게 조정하면 공백으로 채워짐, 현재 문자열보다 짧게 조정하면 나머지 문자는 삭제

 

최근 그리디 문제를 풀면서 생각하는 건데 이전에 푼 문제의 형식에 너무 얽메이지 말고 상식적으로 생각하는 방식이 옳은 방식인 것 같았다. 그리고 머리로 한번에 제대로 생각되지 않는 복잡한 방식임에도 굳이 한번의 문장으로 처리하고 싶으하는 습관이 있는 것 같아 좀 더 원시적인 방식으로 처리하는 것도 나쁘지 않은것 같다고 생각했다.

해결 과정

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String a = reader.readLine();
        String b = reader.readLine();

        while(b.length() != a.length()){
            if(b.charAt(b.length()-1) =='A') {
                b = remove(b);
            }else{
                b = remove(b);
                b = new StringBuilder(b).reverse().toString();
            }
        }

        if(a.equals(b)){
            System.out.println(1);
        }else{
            System.out.println(0);
        }


    }

    static String remove(String str) {
        return str.substring(0, str.length() - 1);
    }
}