문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/67258?language=python3
코딩테스트 연습 - 보석 쇼핑
["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] [3, 7]
programmers.co.kr
진열된 순서대로 보석의 이름이 저장된 list가 매개변수로 주어질 때,
모든 종류의 보석을 1개 이상 포함하는 가장 짧은 구간을 반환하는 문제였습니다.
(가장 짧은 구간이 여러 개 있다면 구간의 시작점이 가장 왼쪽에 있는 경우를 반환합니다.)
이번 문제에는 정확성 테스트와 효율성 테스트가 별개로 존재합니다.
1) 모든 경우를 탐색할 경우
진열된 보석의 정보가 저장된 매개변수 gems이 주어집니다. (gems의 최대 길이는 100,000 입니다.)
탐색할 구간의 왼쪽 끝을 L, 오른쪽 끝을 R이라 하면
탐색의 횟수가 gems의 최대 길이의 제곱에 근사하므로 시간 초과 판정을 받게 됩니다.
부분 점수라도 노린다면 완전 탐색을 구현하는 것이 좋지만 고득점을 노린다면 더 나은 풀이를 고민하는 것이 좋을 것 같습니다.
def solution(gems):
L = 0
cnt_gem_kinds = len(set(gems))
answer = [0, len(gems)-1]
while L < len(gems):
R = L
while R < len(gems):
gem_set = set(gems[L:R+1])
if len(gem_set) == cnt_gem_kinds:
if answer[1]-answer[0] > R-L:
answer = [L, R]
break
R += 1
L += 1
answer[0] += 1
answer[1] += 1
return answercnt_gem_kinds에는 보석의 종류 가지수가 저장됩니다.
R을 하나씩 늘려가며 탐색 멤버를 탐색하고 L과 R 사이에 모든 보석의 종류가 포함되어 있다면
answer와 구간 길이를 비교하여 answer를 갱신합니다.
정확성 테스트에서도 시간 초과 판정을 받았습니다. R을 하나씩 늘리는 과정에서 새로 추가되는 보석인지 확인하도록 최적화 할 수 있을 것 같습니다.
2) 우선순위 큐 사용
모든 보석의 위치를 저장하는 우선순위 큐를 이용하는 방법입니다. (이 때 minHeap을 사용합니다.)
보석의 위치가 이미 저장되어 있으므로 모든 보석을 포함하는 다음 구간을 빠르게 찾을 수 있습니다.
입출력 예 1번으로 주어진 입력값으로 예시를 들어 설명하겠습니다.
입출력 예 1)
gems = ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"]
모든 종류의 보석에 대해서 각각 우선순위 큐를 생성하고 작은 인덱스를 저장합니다.
gems_dict = defaultdict(list)
for i, gem in enumerate(gems):
hq = gems_dict[gem]
heapq.heappush(hq, i)
gems_dict에는 위와 같은 data가 저장됩니다.
모든 보석을 포함하는 구간은 가장 왼쪽에 있는 DIA(0), 가장 오른쪽에 있는 SAPPHIRE(6)으로 구할 수 있습니다.
다음 구간을 탐색하기 위해서 가장 왼쪽에 있는 DIA가 다음에 등장하는 위치로 탐색 위치를 옮깁니다.
DIA가 다음에 등장하는 위치는 RUBY보다 큽니다.
이 경우 가장 왼쪽에 있는 RUBY(1), 가장 오른쪽에 있는 SAPPHIRE(6)으로 구간이 이전 구간보다 길이가 짧으므로
answer가 갱신됩니다.
같은 방식으로 매번 가장 왼쪽에 있는 보석을 pop하고 보석의 위치를 정렬합니다.
그 후 answer보다 구간의 길이가 짧다면 answer를 갱신합니다.
from collections import defaultdict
import heapq
def solution(gems):
gems_dict = defaultdict(list)
for i, gem in enumerate(gems):
hq = gems_dict[gem]
heapq.heappush(hq, i)
line = sort(gems_dict)
answer = [line[0][1], line[-1][1]]
L = line[0][0]
while len(gems_dict[L]) > 1:
hq = gems_dict[L]
heapq.heappop(hq)
line = sort(gems_dict)
L = line[0][0]
if answer[1]-answer[0] > line[-1][1]-line[0][1]:
answer = [line[0][1], line[-1][1]]
answer[0] += 1
answer[1] += 1
return answer
def sort(gems_dict:defaultdict):
gems_list = []
for gem in gems_dict.keys():
gems_list.append((gem, gems_dict[gem][0]))
gems_list.sort(key=lambda x:x[1])
return gems_list
보석의 위치가 미리 저장되어 있어 다음 탐색 위치를 찾기 쉬운 만큼
시간 초과 판정이 줄었지만 여전히 많은 테스트 케이스에서 시간 초과 판정을 받아 합계 점수가 낮습니다.
매번 탐색할 때마다 인덱스 순으로 정렬하는 sort 메서드를 최적화하여 문제를 해결할 수 있을 것 같습니다.
3) 구간에 대한 우선순위 큐 사용
보석 별로 우선순위 큐를 사용해서 탐색 범위를 좁힐 수 있었습니다.
이제는 탐색 구간이 변경될 때마다 가장 왼쪽 인덱스와 오른쪽 인덱스를 찾기 위해 정렬하던 방식을 최적화합니다.
가장 왼쪽에 있던 보석을 pop하면서 오른쪽 인덱스를 최댓값으로 갱신하고
전체 구간에 대한 우선순위 큐를 사용하여 새로운 왼쪽 인덱스 값을 빠르게 구합니다.
from collections import defaultdict
import heapq
def solution(gems):
gems_dict = defaultdict(list)
for i, gem in enumerate(gems):
hq = gems_dict[gem]
heapq.heappush(hq, i)
gems_hq = []
right_end = 0
for gem in gems_dict.keys():
heapq.heappush(gems_hq, (gems_dict[gem][0], gem))
right_end = max(right_end, gems_dict[gem][0])
answer = [gems_hq[0][0], right_end]
while True:
left_end, gem = heapq.heappop(gems_hq)
heapq.heappop(gems_dict[gem])
if len(gems_dict[gem]) == 0:
break
right_end = max(right_end, gems_dict[gem][0])
heapq.heappush(gems_hq, (gems_dict[gem][0], gem))
if answer[1]-answer[0] > right_end-gems_hq[0][0]:
answer = [gems_hq[0][0], right_end]
answer[0] += 1
answer[1] += 1
return answer
최적화 과정을 거쳐 모든 테스트 케이스에서 정답 처리를 받았습니다.
어떻게 하면 탐색 범위를 좁힐 수 있는지 고민하면서 두 번째 풀이를 떠올렸고
매번 인덱스를 처음부터 정렬할 필요가 없다는 사실에 접목하여 세 번째 풀이를 떠올렸습니다.
한 단계씩 문제를 해결하기 위한 방법을 생각해 나가는 재미가 있는 좋은 문제였습니다.