문제 이해하기
두 문자열 s와 t, 그리고 두 개의 값 p와 q가 주어졌다고 가정해 보겠습니다. 이때 다음 조건에 따라 s로부터 t를 만들 수 있는지 확인해야 합니다.
- 문자열 s를 길이 p씩의 그룹으로 나눕니다. 단, 마지막 그룹의 길이는 p 이하일 수 있습니다.
- 각 그룹에서는 최대 q개의 문자만 선택할 수 있습니다.
- t에 등장하는 문자들의 순서는 반드시 s에서의 순서와 동일해야 합니다.
예를 들어 입력이 s = "mnonnopeqrst", t = "moprst", p = 5, q = 2라면 결과는 True입니다. s를 "mnonn", "opeqr", "st" 세 그룹으로 나눈 뒤, 첫 번째 그룹에서 "mo"를, 두 번째 그룹에서 "pr"을 가져오고, 마지막 그룹은 이미 "st"이므로 그대로 사용하면 이들을 단순히 연결하여 t인 "moprst"를 만들 수 있기 때문입니다.
해결 전략
이 문제는 각 문자를 앞에서부터 차례로 배치하면서 그룹별 사용량을 추적하는 그리디 방식으로 해결할 수 있습니다. 알고리즘은 다음과 같습니다.
- temp := 키마다 빈 리스트를 값으로 가지는 딕셔너리(맵)를 생성합니다.
- l := s의 길이와 같은 크기의 리스트를 만들고 0으로 채웁니다. 각 그룹에서 사용된 문자 수를 기록하는 용도입니다.
- i를 0부터 s의 길이까지 반복하면서 i를 temp['a'] 리스트의 끝에 삽입합니다.
- low := 0으로 초기화합니다.
- i를 0부터 t의 길이 - 1까지 반복합니다.
- indices := temp['a']를 가져옵니다.
- it := indices 리스트에서 정렬된 순서를 유지하며 low를 삽입할 수 있는 위치를 찾습니다.
- it이 indices의 크기와 같다면 더 이상 사용할 수 있는 문자가 없다는 의미이므로 False를 반환합니다.
- count := indices[it]를 p로 나눈 몫, 즉 현재 문자가 속한 그룹 번호입니다.
- l[count] := l[count] + 1로 해당 그룹의 사용 카운트를 증가시킵니다.
- l[count] >= q라면 해당 그룹의 할당량을 모두 사용한 것이므로 count := count + 1, low := count * p로 설정하여 다음 그룹으로 넘어갑니다.
- 그렇지 않다면 low := indices[it] + 1로 설정하여 현재 그룹 내에서 다음 문자를 계속 찾습니다.
- 모든 문자를 성공적으로 배치했다면 True를 반환합니다.
여기서 bisect_left를 활용하면 정렬된 인덱스 목록에서 low 이상인 첫 번째 위치를 로그 시간에 찾을 수 있어 전체 탐색 효율이 크게 향상됩니다.
구현 예제
아래 구현을 통해 더 잘 이해해 보겠습니다.
from bisect import bisect_left
from collections import defaultdict
def solve(s, t, b, m):
temp = defaultdict(list)
l = [0] * len(s)
for i in range(len(s)):
temp['a'].append(i)
low = 0
for i in range(len(t)):
indices = temp['a']
it = bisect_left(indices, low)
if it == len(indices):
return False
count = indices[it] // b
l[count] = l[count] + 1
if l[count] >= m:
count += 1
low = count * b
else:
low = indices[it] + 1
return True
s = "mnonnopeqrst"
t = "moprst"
p = 5
q = 2
print(solve(s, t, p, q))입력
"mnonnopeqrst", "moprst", 5, 2
출력
True