백준 (BOJ) 13019 A를 B로 java 그리디

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

13019번: A를 B로

 

이번 문제는 풀기 위한 아이디어가 독특했다. 자세히 남겨보자.

 

예를 들어,

 

original:  DACB

target:    BADC

 

이렇게 있다고 하자.

 

문제의 특성상 문자열 뒤에서부터 접근하면, B와 C를 비교하게 된다. (맨 앞으로 문자를 옮기는 것이기 때문이다.)

 

둘은 다르므로 original의 B를 맨 앞으로 옮기게 되는 연산을 한다. 옮긴 횟수를 나타내는 count가 하나 증가한다.

 

여기서 문제를 풀기 위해 주목할 부분이 있는데 과연 이 B는 어디로 옮겨지게 될까 하는 것이다.

 

만약 B를 맨 앞에 정직하게 붙여 BDAC로 만들었다고 하자.

 

그리고 이 로직으로 한번 쭉 진행해보자. DACB → BDAC → ABDC → BADC 가 된다.

 

3번 바꾼다.

 

하지만, 사실 이 경우 답은 DACB → ADCB → BADC이다. 즉 2번 이동한다.

 

머리로는 이해가 가지만 이렇게 해서는 구현할 때 ?가 남발하게 된다. 

 

그래서 고안해낸 생각은 이렇다.

 

DACB → B_DAC → BADC 이다.

 

결국 자리에 맞지 않는 문자는 최적의 자리를 찾아 가상의 위치에 배치한다고 가정한다. 우리는 항상 최적의 답만 찾는 천재이기 때문이다. 왜냐하면 최소의 횟수를 탐색하는 중이기 때문이다.

 

이렇게 하면 위의 문자열 순차접근을 극복하게 된다. 사실은 DACB → ADCB → BADC 이렇게 이동했겠지만 결국 똑같은 동작을 하게 되는 것이다.

 

origin과 target의 문자열이 다른 경우를 비교하는 로직은 충분히 다르게 짤 방법이 많을 것 같다.

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

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

        // 원소 검사
        int[] alpha = new int[100];
        for (int i=0; i< origin.length(); ++i){
            ++alpha[origin.charAt(i)];
            --alpha[target.charAt(i)];
        }
        for (int i=65; i<91; ++i){
            if(alpha[i] != 0){
                System.out.print(-1);
                return;
            }
        }

        int moveCount = 0;
        int o_idx = origin.length()-1;
        int t_idx = target.length()-1;
        for (; 0<=o_idx; --o_idx){
            if(target.charAt(t_idx) != origin.charAt(o_idx)){
                ++moveCount;
            }
            else{
                --t_idx;
            }
        }

        System.out.print(moveCount);

    }
}