문제 링크
https://www.acmicpc.net/problem/24524
접근
아이디어를 생각하는 것이 은근 까다로웠던 문제였다
일단 문자열 s 의 최대 길이는 100만으로 꽤 크다. O(NlogN) 이하의 복잡도를 가진 알고리즘을 생각해야 한다.
그리고 문자열 t는 길어봤자 26이므로 이를 잘 활용하면 좋을 것 같다고 생각했다.
풀이
나의 풀이의 핵심은 l[k] 리스트이다.
어떤 것인지 설명하고자 우선 코드를 보자.
s = input()
t = input()
l = [0 for _ in t] # l[k] = t[k]까지 있는 것의 개수
t_set = set(t) # 확인하기 편하게 만든 것l[k] 는 아름다운 문자열 t의 k번째 문자열까지 완성이 가능한 것의 개수이다.
문자열 s를 순서대로 보면서 그 값이 t의 k번째 문자열까지 완성시킬 수 있는지 알아보는 것인데... 말로 하면 좀 복잡한 것 같다.
풀이에 대한 코드는 다음과 같다.
for x in s: # s에 대해 순회
if x in t_set: # x가 일단 t안에 있으므로 go!
if x == t[0]: # idx == 0 인 경우
l[0] += 1
else:
idx = t.find(x) # 현재 x 는 t의 몇번째 idx인지 반환
if l[idx - 1]: # t[idx-1] 까지 만들 수 있었다면
l[idx - 1] -= 1 # t[idx-1] 까지 만들 수 있는 경우의 수 하나를 빼고
l[idx] += 1 # t[idx] 까지 만들 수 있는 경우의 수로 편입
주어진 예제 입력인 s = "aabb" 와 t = "ab" 의 경우로 설명하겠다.
먼저 문자열 s의 첫번째 문자 'a'를 보자.
'a' 는 t의 0번째 문자와 같으므로 l[0] +=1 을 해준다. 현재까지는 t[0]까지 하나 완성시킬 수 있다는 뜻이다.
문자열 s의 두번째 문자 'a'를 보자.
이번에도 'a' 는 t의 0번째 문자와 같으므로 l[0] +=1 을 해준다.
l[0] == 2이므로 현재까지 t[0]까지 두개 완성시킬 수 있다는 뜻이다.
문자열 s의 세번째 문자 'b'를 보자.
'b' 는 t의 1번째 문자와 같다(idx=1). 여기서 우리는 t[1]까지 만들 수 있는지, 즉 l[1]을 증가시켜도 되는지 먼저 확인해야한다.
방법은 간단하다. l[idx-1] 을 확인하고, 값이 1 이상 있으면 t[idx] 까지 만들 수 있는 것이다.
그러면 l[idx-1] 을 하나 감소시키고 l[idx] 을 하나 증가시킨다. 기존의 t[idx-1]까지 만들 수 있는 경우의 수 하나가 t[idx] 까지 만들 수 있는 경우의 수로 옮겨갔다고 생각하면 편하다.
마지막 s의 네번째 문자 'b'도 세번째와 같다.
l[0]==1 이므로 l[0]을 하나 빼주고, l[1] 을 하나 더한다.
그러므로 최종적으로 l[1] == 2가 되어 답 2를 얻을 수 있다.
정답 코드
s = input()
t = input()
cnt = 0
l = [0 for _ in t] # l[k] = t[k]까지 있는 것의 개수
t_set = set(t)
for x in s:
if x in t_set: # x가 일단 t안에 있음
if x == t[0]: # idx == 0 인 경우
l[0] += 1
else:
idx = t.find(x) # t[idx] == x
if l[idx - 1]:
l[idx - 1] -= 1
l[idx] += 1
print(l[-1])
