문제 링크
https://programmers.co.kr/learn/courses/30/lessons/67258
문제 설명
배열의 크기가 10만 이하이므로 시간 복잡도를 고려하여 풀어야하는 문제이다. 슬라이딩 윈도우(투 포인터) 알고리즘을 사용하였다.
1. 초기값 설정
start, end 인덱스 모두 인덱스 0에서 시작하는 것으로 세팅한다.
dic[gems[start]] +=1 , 즉 dic['DIA']에 +1을 해준다. 이 때, 처음 갖는 보석이므로 check_num += 1 하여 가지고 있는 보석의 종류를 관리하였다.
2. 가지고 있는 보석의 종류가 충족되지 않는 경우
end 포인터를 1씩 늘려가며 가지고 있는 보석의 종류를 체크한다.
3. 가지고 있는 보석의 종류가 충족된 경우
start인덱스와 end 인덱스 사이 구간 값을 확인 -> 더 짧은 구간인 경우 갱신 -> start 포인터 1씩 늘리며 확인을 반복한다.
"가장 짧은 구간의 시작 진열대 번호와 끝 진열대 번호를 차례대로 배열에 담아서 return 하도록 하며, 만약 가장 짧은 구간이 여러 개라면 시작 진열대 번호가 가장 작은 구간을 return 합니다." 라는 조건이 있으므로, 순서대로 확인하되 짧은 구간일 경우 갱신해주면 된다.
문제 코드
def set_dic(gems):
result = {}
for gem in gems:
result[gem] = 0
return result
def solution(gems):
answer = []
min_val = 100000
dic = set_dic(gems)
#초기값 설정
start, end = 0, 0
dic[gems[start]] += 1
check_num = 1
while True:
if check_num == len(dic):
if min_val > end-start:
min_val = end-start
answer = [start+1, end+1]
#start 포인터 값 제외
dic[gems[start]] -= 1
if dic[gems[start]] == 0:
check_num -= 1
#start 포인터 한 칸 앞으로
start += 1
if start >= len(gems):
break
else:
#end 포인터 한 칸 앞으로
end += 1
if end >= len(gems):
break
#end 포인터 값 추가
dic[gems[end]] += 1
if dic[gems[end]] == 1:
check_num += 1
return answer정확성 테스트
테스트 1 〉 통과 (0.02ms, 10.2MB)
테스트 2 〉 통과 (0.06ms, 10.3MB)
테스트 3 〉 통과 (0.21ms, 10.3MB)
테스트 4 〉 통과 (0.19ms, 10.3MB)
테스트 5 〉 통과 (0.35ms, 10.3MB)
테스트 6 〉 통과 (0.01ms, 10.3MB)
테스트 7 〉 통과 (0.01ms, 10.3MB)
테스트 8 〉 통과 (0.34ms, 10.3MB)
테스트 9 〉 통과 (0.53ms, 10.4MB)
테스트 10 〉 통과 (0.39ms, 10.3MB)
테스트 11 〉 통과 (0.77ms, 10.4MB)
테스트 12 〉 통과 (0.90ms, 10.3MB)
테스트 13 〉 통과 (1.31ms, 10.4MB)
테스트 14 〉 통과 (1.23ms, 10.6MB)
테스트 15 〉 통과 (2.39ms, 10.5MB)
효율성 테스트
테스트 1 〉 통과 (2.89ms, 10.6MB)
테스트 2 〉 통과 (5.35ms, 10.6MB)
테스트 3 〉 통과 (10.46ms, 11.2MB)
테스트 4 〉 통과 (8.56ms, 11.7MB)
테스트 5 〉 통과 (15.56ms, 11.9MB)
테스트 6 〉 통과 (20.28ms, 12.2MB)
테스트 7 〉 통과 (22.40ms, 12.7MB)
테스트 8 〉 통과 (28.26ms, 13MB)
테스트 9 〉 통과 (30.45ms, 13.5MB)
테스트 10 〉 통과 (35.24ms, 13.8MB)
테스트 11 〉 통과 (38.75ms, 14.6MB)
테스트 12 〉 통과 (27.95ms, 15.5MB)
테스트 13 〉 통과 (40.67ms, 16.4MB)
테스트 14 〉 통과 (67.70ms, 17.2MB)
테스트 15 〉 통과 (65.69ms, 17.8MB)