보석 쇼핑 풀이
보석 쇼핑 문제 바로가기 코딩 테스트에서 시간잡아먹는 비율이 코딩 10%, 알고리즘 고안 90% 인것같다. 특히나 효율성이 포함된 문제라면…
이문제에서 효율성의 핵심은 Dictionary를 이용하는 것이다.
커서가 이동하며 장바구니(Dictionary)안에 모든 보석종류가 들어올때 까지 R 커서가 오른쪽으로 이동하고, 모든 보석 종류가 장바구니안에 들어오면 왼쪽커서를 오른쪽으로 이동시키며 범위를 줄여나간다.
최종 정답은 정답 후보중 가장 길이가 짧은(R - L) [L, R]을 return하는 것이다.
그리고 장바구니의 보석이 0개가 되면 삭제를 시켜주어야하고, 이미 있는 보석이면 +1 해주어야한다. 왜냐하면 이 문제에서 효율성을 판단하는 핵심이 바로 장바구니의 사이즈로 모든 종류의 보석을 샀는지를 판단해야하기 때문이다.
**
코드
def solution(gems):
products = list(set(gems))
l = 0
r = 0
bucket = {}
answer = [0, len(gems)]
while(l <= len(gems) and r <= len(gems)) :
if len(bucket) == len(products) :
if answer[1]-answer[0] > r-l:
answer = [l, r]
bucket[gems[l]] -= 1
if bucket[gems[l]] == 0 : del bucket[gems[l]]
l += 1
else :
try :
if gems[r] in bucket : bucket[gems[r]] += 1
else : bucket[gems[r]] = 1
except :
break
r += 1
answer[0] += 1
return answer
사야할 보석 종류 리스트 구하기
보석을 몇종류 사야하는지를 set을 이용하여 구해줍니다.
products = list(set(gems))
커서와 장바구니
그리고 초기 커서 l, r과 장바구니 bucket, 그리고 초기 답은 진열대 전체 처음부터 끝까지 [0, len(gems)]로 초기화
그리고 조금 헷갈릴 수 있는 부분이 커서의 범위와 리스트 인덱싱이 끝부분에서 1 차이가 납니다.
파이썬 인덱싱은 인덱스 숫자부터 인덱스 숫자 전까지 나타내기때문에(
list[3:8]은 3번부터 7번까지 를 나타냄)
l = 3,r = 8이것을[3번보석, 8번보석]으로 볼 것인지,[3번보석, 7번보석]으로 볼것인지 잘 정해서 코딩을 해야합니다(저는 전자로 함). 저도 이것 때문에 대가리가 깨질 뻔했습니다.
l = 0
r = 0
bucket = {}
answer = [0, len(gems)]
쇼핑 시작
while(l <= len(gems) and r <= len(gems)) :
우선 반복문 종료조건부터 지정해줍니다. 저는 l = 3, r = 8 이것을 [3번보석, 8번보석] 으로보는 방식을 선택 했으므로 인덱스 l과 r이 gems의 배열 길이를 초과해야 반복을 종료하도록 했습니다.
while(l <= len(gems) and r <= len(gems)) :
if len(bucket) == len(products) : # 장바구니에 살꺼 다 샀음. l커서 움직이기
l += 1
else : # 아직 살꺼 다 못삼. r커서 움직이기
r += 1
커서가 움직이는 2가지경우의 수를 조건문으로 넣고
while(l <= len(gems) and r <= len(gems)) :
if len(bucket) == len(products) :
if answer[1]-answer[0] > r-l : answer = [l, r] #기존 정답과 비교해 더좋으면 교체
l += 1
else :
r += 1
현재 정답과 기존정답의 길이를 비교해 현재 정답이 더 좋으면 교체해주도록 합니다.
이제 남은것은 장바구니의 최신화입니다.
r커서를 움직이는 경우
- 이미 장바구니에 있으면 보석갯수를 추가
- 새로운 보석이면 장바구니에 새로 추가
l커서를 움직이는 경우
- 보석 갯수가
0이 되면 그 보석은 장바구니에서 삭제
이 2가지가 장바구니 최신화의 핵심 입니다.
while(l <= len(gems) and r <= len(gems)) :
if len(bucket) == len(products) :
if answer[1]-answer[0] > r-l:
answer = [l, r]
bucket[gems[l]] -= 1
if bucket[gems[l]] == 0 : del bucket[gems[l]] # 0이되면 삭제
l += 1
else :
try :
if gems[r] in bucket : bucket[gems[r]] += 1 # 기존에 있으면 +1
else : bucket[gems[r]] = 1 # 새로운 보석이면 새로 추가
except : break
r += 1
이렇게 조건에 맞게 장바구니 최신화를 시키고, try-catch는 인덱싱과 인덱스 사이의 괴리감때문에 넣게되었습니다.
예를 들어, gems의 길이가 10 일때 gems는 0~9까지의 인덱스를 가지고 있습니다.
커서 하나로 gems[index] 와 gems[:index]를 처리하니 탈출문에서 문제가 생겼는데, try-catch를 쓰지 않으면 코드가 깔끔해지지가 않아서 어쩔 수 없이 쓰게 되었습니다.