20191번: 줄임말
문자열 A가 문자열 B의 줄임말이라는 것은 B의 순서를 바꾸지 않고 0 또는 그 이상 개수의 문자를 지워 A를 만들 수 있다는 뜻이다. 정의에 의해서 B는 자기 자신의 줄임말임에 유의하라. 예를 들
www.acmicpc.net
from bisect import bisect_right, bisect_left
if __name__ == '__main__':
s = input()
t = input()
# s = 'caa'
# t = 'ac'
next = [[] for _ in range(26)]
for i in range(len(t)):
next[ord(t[i]) - ord('a')].append(i)
def solution(ss):
ans = 1
pos = -1
before_pos = -1
for y in ss:
k = ord(y) - ord('a')
if not next[k]:
return -1
pos = bisect_right(next[k], before_pos)
if pos == len(next[k]):
ans += 1
pos = 0
before_pos = next[k][pos]
return ans
if s == t:
print(1)
else:
print(solution(s))
하... 이 문제는 정말 뇌정지가 오는 문제였다. 우선 위 코드는 100점짜리 풀이다.
처음 문제만 보고 만만하게 생각했다가 덤벼들었는데, 첫제출은 틀렸고 두번째 제출에 13점을 맞았다.
13점 풀이:
그냥 T를 처음부터 끝까지 순회하면서 S와 동일한 문자가 나오면 S의 포인터를 1씩 증가시켜주다가
T의 끝에 도착했는데 S의 포인터가 S의 길이와 동일하지 않다면 줄임말이 완성되지 않은것이므로 T에 T를 이어붙이고 결과값을 1 증가시킨후, 이어서 순회한다.
42점 풀이:
기본적으로는 13점 풀이와 비슷하나, T의 끝에 도착했는데 S의 포인터가 S의 길이와 동일하지 않다면 T에 T를 이어붙이는것이 아니라, T의 처음으로 보내서 다시 찾는다.
68점 풀이 (여기서부터 다른 분의 해설을 참고):
42점보다 효율을 더 높이려면 전처리를 해야한다. 전처리를 함으로써 얻을 수 있는 이점이 뭐냐하면 T를 한칸한칸 이동하면서 줄임말이 있는지 없는지 찾는게 아니라, S를 한칸씩 이동하면서 T에 해당 문자가 존재하면 그 위치로 한번에 이동할 수 있게 된다.
우선 전처리를 하려면 문제를 잘봐야하는데 문제에 보면 T와 S는 a-z 까지의 소문자'만'으로 이뤄진다고 명시돼있다. a-z 까지는 26자 밖에 되지 않으므로 전처리하기에 유리하다.
우선 이차원 배열을 하나 만드는데 만든 배열이 word[a][b] 라고 가정하자
여기서 a 는 T의 문자열길이의 크기를 가지며 b 는 26 즉 알파벳 a-z 의 길이를 갖는다.
이 배열에는 T 의 각 위치에서 a 에서 z까지 문자의 위치 인덱스를 저장한다.
만약 T 가 nice 라고 한다면 아래와 같이 저장된다. 여기서 -1은 존재하지 않는 문자다
[-1, -1, 2, -1, 3, -1, -1, -1, 1, -1, -1, -1, -1, 0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1]
[-1, -1, 2, -1, 3, -1, -1, -1, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1]
[-1, -1, 2, -1, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1]
[-1, -1, -1, -1, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1]
배열의 첫번째 행은 nice 중 각 문자의 위치
배열의 두번째 행은 ice 중 각 문자의 위치
배열의 세번째 행은 ce 중 각 문자의 위치
배열의 네번째 행은 e 중 각 문자의 위치가 들어간다.
배열의 첫번째 행을 보면 nice 중 각 문자의 위치를 저장하는데
[-1, -1, 2, -1, 3, -1, -1, -1, 1, -1, -1, -1, -1, 0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1]
-> nice 에 a는 없고 b는 없고 c는 2번 인덱스에 있고 d는 없고 e는 3번 인덱스에 있고 n은 0번 인덱스에 있다는 뜻이다.
이렇게 T의 각 위치에서의 a부터 z까지의 위치 인덱스를 미리 저장해놓으면 S를 순회하면서
정해진 위치를 한번에 알 수 있게된다.
어떻게 한번에 알 수 있냐면
S = 'in' 이라고 가정하고 간단히 첫번째 순회를 살펴보자.
첫번째 순회이기때문에 T의 0번째 문자부터 확인을 해야하므로 우선 word[0] 은 확정이고
S[0]이 무슨 문자냐에 따라 두번째 배열의 위치를 알 수 있는데 ord(S[0]) - ord('a') 와 같이 처리하면 a라면 0. b 라면 1 c 라면 2 ... 를 얻게 된다.
S[0]은 i 이므로 8을 얻게되고 word[0][8] 을 확인해보면 1이다. T의 1 번째에 i가 있다는 소리다.
일단 i는 T의 1번째에서 찾았으니 이제 T의 2번째 문자에서부터 n이 존재하는지 찾으면 된다.
n = 13 이므로
word[2][13]을 확인해보면 -1 이다. 즉 T의 2번째 문자부터 더이상 n은 없다는 뜻이다.
이 경우, 결과값을 1 증가시켜주고 위치를 0으로 바꿔준다. 결과값을 1 증가시켜줬다는건 문자를 한번 이어붙였다는 뜻이고 위치를 0 으로 바꿔준다는건 문자를 이어붙였으니 다시 처음부터 탐색한다는 뜻이다.
이제 다시 word[0][13]을 확인해보면 0 이다. n은 0번째에 있다.
이제 i 와 n 을 다 찾았으니 결과를 출력해주면된다.
이게 68점짜리 풀이다.
이거 푸는데 풀이를 참고했음에도 불구하고 죽는줄 알았다.. ㅡ.ㅡ
if __name__ == '__main__':
s = input()
t = input()
# s = 'cab'
# t = 'acca'
next = [[-1] * 26 for _ in range(len(t))]
for i in range(len(t)):
for j in range(i, len(t)):
idx = ord(t[j]) - ord('a')
if next[i][idx] == -1:
next[i][idx] = j
def solution(ss):
ans = 1
idx = 0
matched = 0
for i in ss:
c_idx = ord(i) - ord('a')
if idx >= len(next):
ans += 1
idx = 0
idx = next[idx][c_idx]
if idx == -1:
ans += 1
idx = next[0][c_idx]
if idx == -1:
return -1
matched += 1
else:
matched += 1
idx += 1
return ans
print(solution(s))
100점 풀이 (다른분의 풀이 와 소스 모두 참고):
자.. 68점풀이에서 할만큼 한것같은데 여기서 더 효율을 어떻게 높이면 좋을까.
n은 S의 길이를 순회하며 줄임말을 찾는데 걸리는 시간이고, m은 T의 길이를 순회하며 모든 알파벳의 위치를 저장하는 전처리 작업에 드는 시간이라고 했을때 n은 줄일수가 없다. 만들어야하는 줄일말이 뭔지는 알아야하니 무조건 S의 길이만큼은 순회를 해야한다.
그렇담 m을 줄여야한다는 소린데 .. 전처리를 하려면 T를 이중 for문으로 순회해야하기 때문에 O(M^2) 이다. 줄일곳은 이곳밖에 없다.
전처리를 할때 68점의 풀이처럼 T의 각 위치별 모든 알파벳의 위치를 담는게 아니라,
a부터 z까지가 T의 어느 위치에 있는지만 저장하면 전처리 시간을 줄일 수 있다.
word[a][b] 일때, a는 a-z의 크기인 26으로 설정 b는 빈 리스트를 설정한후,
happyday 인 경우 word는 아래와같이 저장된다.
[1, 6]
[]
[]
[5]
[]
[]
[]
[0]
[]
[]
[]
[]
[]
[]
[]
[2, 3]
[]
[]
[]
[]
[]
[]
[]
[]
[4, 7]
[]
a = 1, 6 번 인덱스에, d = 5 번 인덱스에, h = 0 , p = 2,3 y = 4, 7 인덱스에 존재한다는 뜻이다.
이렇게 저장했다면 이제 S를 순회하면서 각 문자가 존재하는지를 찾아야하는데 S = 'pay' 라고 가정하자.
우선 p를 찾는데 T(happyday) 의 첫 위치 부터 찾아야한다.
T에서 p의 위치를 확인하기위해 word[15] 를 보니 2와 3이 있다. 즉 T의 2번째와 3번째 인덱스에 p가 있다는 것이다.
이 2와 3중에 어느걸 써야할지를 알기 위해서 이전에 탐색했던 글의 위치를 알아야한다.
이 글을 보고 첫순회니 당연히 첫번째 요소인 2를 써야지 라고 생각할 수 있는데
만약 T 와 S 의 길이가 10000 글자 이상이고 지금 S의 500번째 위치의 p를 찾아야하는 시점이라면 word[15]엔 엄청 많은 인덱스값이 들어있을거고 어느걸 어떻게 찾아야할지 감이 잘 오지 않을것이다.
이때 중요한 알고리즘이 하나 등장하는데 바로 이진 탐색(이분탐색 또는 binary search 라고도 한다)이다.
오름차순으로 정렬된 List 에서 특정 값 x 가 어느 위치에 들어가야하는지를 아주 빠르게 찾는 알고리즘이다.
이 문제로 다시 돌아와서 초기값을 -1 로 설정하고 특정 값 x의 오른쪽 위치 인덱스를 찾는 binary_right 를 이용하면 -1의 오른쪽인 0을 찾을 수 있고, 이 경우 2 번째 인덱스에 있는 p를 찾아낸다.
찾아냈으면 이 위치를 이전에 탐색했던 글의 위치 변수 에 저장해놓는다.
다음 순회 시 a를 찾을 때 word[0] 을 보면 1,6 이 있는데, 이전에 탐색했던 위치 2가 삽입될 위치의 오른쪽 인덱스 . 즉 T의 2번째 이후에 a 가 등장하는 인덱스를 이진탐색으로 찾아낸다. 이 경우 2가 삽입될 오른쪽 위치 인덱스는 1이다. 그럼 이 경우 6번째 인덱스의 a를 찾아내게 된다.
다음 순회인 y를 찾을 때 word[24] 를 보면 4, 7 이다. 즉 T의 4번째와 7번째 인덱스에 y가 있다는 소리다.
이전에 탐색했던 위치가 6이다 4,7 에서 6이 들어갈 위치의 오른쪽 인덱스를 이진탐색으로 찾아보면 1이다. 0번째 인덱스가 4고 1번째에 있는 인덱스가 7이므로 7번째 인덱스에 있는 y를 찾은것이다.
쉽게 말해 이전에 happyday 의 6번째에서 a 를 찾았다 즉 happyd[a]y 에서 찾았으니 happ[y]da[y] 중 앞쪽에 있는 y말고 뒷쪽에 있는 y를 이용해야 줄임말을 만들 수 있다는 뜻이다.
휴.. 글로 쓰는것도 만만치가 않다. 생각을 말로든 코드로든 꺼내놓는게 쉬운일이 아니다.