줄임말

🤔 시도 1 - 브루트포스

1. s 에 있는 문자가 t에 존재하지 않으면 -1 을 출력하고 프로그램 종료
2. t 문자들을 무한히 순회하면서 s문자를 만들어감.
3. 몇 회 순회하였는지 출력

시간초과가 날 것이라고 어느 정도 예상했다. 예를 들어 s가 yes고 t가 yaaaaaaaaeaaaaaaaaasaaaaaaaa... 라면, 불필요한 연산이 너무 많기 때문이다.

#20191
s = input()
t = input()

if set(s) - set(t):
    print(-1)
    exit()

rn = 0
i = 0
while True:
    word = t[rn % len(t)]
    rn += 1
    if s[i] == word:
        i += 1
    if i == len(s):
        break
    
res = rn // len(t)
if rn % len(t):
    res += 1

print(res)

🤔 시도 2 - deepcopy

알파벳 소문자만 이용하기 때문에 최대 26개뿐이고, 따라서 각 알파벳의 위치 정보를 저장하는 것이 시도 1의 문제점을 해결할 수 있을 것 같다고 생각했다.

1. dp를 이용하여 t의 알파벳 위치 정보를 저장했다.
2. 이때 t를 역순으로 순회하여 같은 알파벳의 위치 정보를 역순으로 저장하였다.
3. dp를 deepcopy한 d를 생성하고, s의 알파벳이 d에 존재할 경우 위치 정보를 하나씩 pop해가는 식으로 풀었다.

   d = copy.deepcopy(dp)

4. 만약 존재하지 않는다면 다시 dp를 deepcopy 한 후 재확인.

deepcopy의 시간복잡도를 전혀 고려하지 않은 코드였다. deepcopy는 시간복잡도가 O(n)으로 결국, 최대 len(s)번 deepcopy를 해야 하는 것이다.

#20191
import copy
# left_t에 해당 알파벳이 있는지 찾는게 우선.

# input
s = list(input())
t = list(input())

dp = [[] for _ in range(26)]


t_i = len(t) - 1
for i in t[::-1]:
    dp_i = ord(i) - 97
    dp[dp_i].append(t_i)

    t_i -= 1

d = copy.deepcopy(dp)

t_i = -1
res = 1
for w in s:
    d_i = ord(w) - 97

    if d[d_i] and d[d_i][-1] > t_i:
        t_i = d[d_i].pop()

    else:
        res += 1
        d = copy.deepcopy(dp)
        t_i = -1
        if d[d_i]:
            t_i = d[d_i].pop()
        else:
            print(-1)
            exit()

print(res)

🤔 시도 3 (정답)

dp를 복제하고 수정하는 것이 불가능 하다면 결국, dp에서 직접 읽어와야 한다고 판단하였다. 그러려면 같은 알파벳에 대하여 여러 위치 정보 중, 바로 이전에 사용한 알파벳의 인덱스 값보다는 큰 위치를 사용하되 최소 위치를 사용해야 한다는 뜻이다. -> binary search

1. t를 순회하면서 알파벳의 위치 정보를 순서대로 저장한다.
2. s를 순회하면서 dp에 해당 문자의 위치 정보를 확인한다.
3. 해당 문자의 위치들 중 현재 포인터 t_i 보다는 큰 위치 중 가장 작은 값을 찾아야 한다.
4. 존재한다면 포인터를 해당 위치로 옮겨주고, 존재하지 않는다면 res += 1 후 t_i 를 -1로 초기화시킨 후 다시 찾는다.
5. 다시 찾아도 없다면 print(-1) 이후 프로그램 종료

이 코드로 정답처리를 받긴 하였지만 다른 사람들의 제출 중 훨씬 더 빠른 제출이 있는 것을 확인하고 다시 풀어보았다.

#20191

#이분탐색
def b_search(d_i, t_i):
    start = 0
    end = len(dp[d_i]) - 1
    res = -1
    while start <= end:
        mid = (start + end) // 2
        if dp[d_i][mid] > t_i:
            res = mid
            end = mid - 1
        else:
            start = mid + 1

    return res

# input
s = list(input())
t = list(input())

dp = [[] for _ in range(26)]
for t_i, i in enumerate(t):
    dp_i = ord(i) - 97
    dp[dp_i].append(t_i)

t_i = -1
res = 1
for i, w in enumerate(s):
    d_i = ord(w) - 97
    tmp = b_search(d_i, t_i) # 없으면 0, 있으면 인덱스
    if tmp >= 0:
        t_i = dp[d_i][tmp]
    else:
        res += 1
        t_i = -1
        tmp = b_search(d_i, t_i) # 없으면 0, 있으면 인덱스
        if tmp >= 0:
            t_i = dp[d_i][tmp]
        else:
            print(-1)
            exit()

print(res)

🤔 시도 4 (최종)

아무리 생각해봐도 더 이상의 효율적인 로직이 생각나지 않아서 다른 분의 코드를 참고하였다. 이전 시도와의 차이점 중 하나는, 이 리스트이든 해시맵으로 바꾼 점이다. 그러나 이전에도 위치 정보에 상수시간으로 접근할 수 있었기 때문에 연산 속도에 큰 차이를 주진 못한다고 생각했다.

결국은 binary search를 직접 구현하지 않고 bisect 라이브러리의 도움을 받아서 연산 속도에 차이가 있었던 것이었다.

이 문제를 풀면서 bisect이라는 라이브러리가 있는 줄 처음 알게 되었다.
bisect 모듈이 binary search를 직접 구현하는 것보다 훨씬 빠른 이유는, c언어로 작성되어 파이썬보다 더 낮은 수준에서 메모리 및 연산을 제어할 수 있기 때문이다.

#20191
from bisect import bisect_left

# input
s = list(input())
t = list(input())

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

t_i = 0
res = 1
for i, w in enumerate(s): 
    tmp = bisect_left(dp[w], t_i)
    if tmp < len(dp[w]):
        t_i = dp[w][tmp]+1
    else:
        res += 1
        t_i = 0
        tmp = bisect_left(dp[w], t_i)
        if tmp < len(dp[w]):
            t_i = dp[w][tmp]+1
        else:
            print(-1)
            exit()

print(res)