[백준] A를 B로

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

13019번: A를 B로

그리디 문제입니다. 그리디 문제에 약해서 풀이까지 애를 먹었습니다. 아이디어는 간단합니다.

먼저 문자열을 정렬해서 비교했을 때 같은 문자들로 구성되어 있지 않으면 아무리 이동시켜도 만들 수 없습니다. 이제 두 문자열은 같은 문자들로 구성이 돼있음이 보장됩니다.

 

다음으로, 이제 A와 B의 뒤에서 부터 문자를 비교하여 같은 경우에는 이동시킬 이유가 없으므로 계속해서 버립니다. 이제 A와 B의 마지막 문자가 다르므로 A에서 이동이 필요합니다. 마지막 문자를 버리고 이동이 필요하므로 answer += 1 해줍니다. 이런 과정을 B의 마지막 문자와 같아질 때까지 반복합니다. 

 

위 과정을 A에 더 이상 문자가 없을 때까지 반복한 다음 answer를 출력하면 됩니다. A와 B는 문자들의 구성이 같고 B의 경우에는 A와 B의 마지막 문자들이 같을 때에만 문자가 버려집니다. 즉, Answer+=1 하면서 앞으로 보내진(버려진) 문자들과 B에 남아 있는 문자들이 같게 되므로 정답이 됩니다. 

 

 

import sys
from collections import deque

# sys.stdin = open("input.txt", "r")

input = sys.stdin.readline

input_a = input().rstrip()
input_b = input().rstrip()

A = deque(input_a)
B = deque(input_b)

answer = 0

# 같은 문자들로 구성되있지 않으면 만들 수 없다.
if sorted(A) != sorted(B):
    print(-1)
    sys.exit(0)

while A:
    # 뒤에서 부터 문자가 같은 경우에는 이동할 필요가 없으므로 버린다.
    while A and B and A[-1] == B[-1]:
        A.pop()
        B.pop()

    if not A:
        break

    # 단순하게 현재 마지막에 위치하는 문자를 비교하여 같지 않으면
    # A에서 날려버린다. 즉, 앞으로 보내버리면 된다.
    while A and B[-1] != A[-1]:
        answer += 1
        A.pop()

print(answer)