[Python 3] BOJ - 20191 "줄임말"

 # 문제 링크

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

20191번: 줄임말

 

 # 풀이

 개인적으로 이 문제의 핵심은 그리디 알고리즘과 이분 탐색이라고 생각한다.

<그림 1. t=aacba인 경우>

 위 그림 1은 t가 "aacba"인 경우를 나타낸 그림이다. 이 때 만일 s의 첫글자가 c인 경우를 생각해보자. 그렇다면, 두번째 글자는 a,b,c 중 하나일 것이다. 그런데 a와 b의 경우는 굳이 n을 증가시키지 않아도 얻을 수 있으나, c의 경우는 n을 증가시켜야만 얻을 수 있다. 따라서 현재 글자에서 다음 글자로 향할 때 다음 글자의 인덱스가 현재 글자의 인덱스보다 더 크다면 굳이 n을 증가시킬 필요가 없다. 그런데 그러한 인덱스가 없다면, 현재 글자의 인덱스보다 작거나 같은 값 중 가장 작은 값을 가져감으로서 n을 1증가시켜야 한다. 그러한 글자 자체가 없다면 아무리 n을 증가시켜도 만들 수 없으므로 -1을 출력하면 된다.

 따라서, 문제를 풀기 위해서는 현재 인덱스 기준으로 가장 가까운 인덱스를 저장하는 배열을 전처리해야 한다.

<그림 2. 전처리 과정>

 위 그림 2는 전처리 과정의 예시를 나타낸 그림이다. temp는 알파벳 소문자를 key, 그 때의 인덱스 리스트를 value로 갖는 딕셔너리이고, cache는 이중 딕셔너리로 1차적으로 인덱스를 key로 갖고, 이후 알파벳 소문자를 다시 2차 key, 최종 value는 현재 인덱스 기준으로 가장 가까운 해당 문자의 인덱스이다. 이 때, 해당 문자는 t에 없다는 의미로 -1을 가질 수 있다. 그런데, n을 증가시키지 않고 가장 가까운 알파벳이 있다면 그것의 위치는 현재 인덱스를 기준으로 하는 upper_bound와 동치이다. 따라서, temp의 value는 항상 정렬된 상태여야 하고, 이분 탐색을 통해 로그 시간만에 구할 수 있다

 따라서, s의 첫문자가 될 수 있는 t의 인덱스 중 가장 빠른 것을 기준으로 전처리 내용을 바탕으로 최소 n을 구할 수 있으며 구성 중 -1이 나온다면 절대로 s를 만들 수 없는 경우이므로 -1을 출력하면 된다

 

 # 코드

import sys, string

# go : 현재 num번째 인덱스를 기준으로 가장 가까운 알파벳 소문자의 인덱스를 저장하는 함수
def go(num):
    for i in string.ascii_lowercase:
        # 현재 알파벳 i가 t에 있다면
        if temp[i]:
            # 이분 탐색
            left = 0
            right = len(temp[i])
            while left < right:
                mid = (left + right) // 2
                if temp[i][mid] <= num:
                    left = mid + 1
                else:
                    right = mid
            # 만일 upper_bound가 없다면 가장 왼쪽 인덱스
            if right == len(temp[i]):
                cache[num][i] = temp[i][0]
            else:
                cache[num][i] = temp[i][right]

# 입력부
s = list(sys.stdin.readline().rstrip())
t = list(sys.stdin.readline().rstrip())
n = len(t)

# cache : 현재 인덱스를 1차 key, 알파벳 소문자를 2차 key, 가장 가까운 인덱스를 value로 하는 2중 딕셔너리
cache = dict().fromkeys([i for i in range(n)])
for i in cache:
    cache[i] = dict().fromkeys(string.ascii_lowercase, -1)
    
# temp : 알파벳 소문자를 key, 그 때의 인덱스 리스트를 value로 갖는 dictionary
temp = dict().fromkeys(string.ascii_lowercase)
for i in temp:
    temp[i] = []
for i in range(n):
    temp[t[i]].append(i)
    
# cache를 go함수를 통해 채운다
for i in range(n):
    go(i)
    
# idx : s의 첫글자의 인덱스, 만일 없으면 -1
idx = t.index(s[0]) if s[0] in t else -1
now = idx[s[0]]
ans = 1
can = True
for i in range(1, len(s)):
    # 현재 인덱스가 -1이라면 그 글자는 없기 때문에 flag변수인 can을 False로 바꾼후 break
    if now == -1:
        can = False
        break
    # 아니라면 다음 문자의 가장 가까운 인덱스로 이동
    else:
        next = cache[now][s[i]]
        # 가장 가까운 인덱스가 현재 인덱스보다 더 작거나 같다면 n을 1 증가
        if next <= now:
            ans += 1
        now = next
if now == -1:
    can = False
    
# 조건에 따른 정답 출력
print(ans if can else -1)