[백준 20191번] 줄임말 (Python3)

import sys
input = sys.stdin.readline
from bisect import bisect_left

S = input().strip()
T = input().strip()

s,t = len(S),len(T)

alphabet = {i:[] for i in "abcdefghijklmnopqrstuvwxyz"}
for i in range(t):
  alphabet[T[i]].append(i)

cnt = 1
last = 0
for letter in S:
  if not alphabet[letter]:
    cnt = -1
    break
  idx = bisect_left(alphabet[letter],last)
  if idx == len(alphabet[letter]):
    cnt += 1
    last = 0
    idx = bisect_left(alphabet[letter],last)
  last = alphabet[letter][idx]+1

print(cnt)

 

이분탐색으로 구현하였다.

 

일단 가장 처음 떠올릴 수 있는 알고리즘은, S의 단어 하나하나를 T에서 찾은다음, 못찾을 때마다 n을 +1씩 해주는 방법이다. T에서 찾는 시간복잡도는 O(T)이기 때문에 모든 단어를 찾으면 시간복잡도는 O(ST)가 될 것이다. S의 최대길이가 100만이고 T의 최대길이가 10만이니 방식으로는 해결할 수 없다.

 

그러다가 예전에 트리의 순회 문제에서 index 함수 대신에 미리 각 숫자의 index를 저장해놓고 불러왔던것이 생각이 났다. T에서 각 알파벳의 위치를 미리 저장해두고, 필요할때마다 풀러오게 되면 T에서 찾는 시간복잡도가 확 줄어들게 될것이다.

 

요약하면

1. T의 모든 알파벳의 위치를 저장한다.

2. S의 각 단어들을 돌면서 T에서의 위치를 찾는다. 이때 위치를 찾는것은 이분탐색을 이용한다.

3. T에서 찾지 못할때마다 cnt를 +1씩 하고 최종 cnt를 출력한다.

 

T에서 찾는 시간복잡도를 O(logT)로 줄였기 때문에 최종 시간복잡도는 O(SlogT)로 구현 가능하다.

 

 

오늘의 교훈) 미리 위치를 처리하는것이 중요하다