[2020 카카오 인턴십] 보석 쇼핑
문제 : https://programmers.co.kr/learn/courses/30/lessons/67258
문제 : 진열된 모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 구간을 찾아서 구매
인덱스를 1부터 시작. 구간의 첫 인덱스와 끝 인덱스를 list로 저장해서 반환
입력 예시 : ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"]
예시 결과 값 : [3, 7]
[제한 사항]
- gems 배열의 크기는 1 이상 100,000 이하입니다.
- gems 배열의 각 원소는 진열대에 나열된 보석을 나타냅니다.
- gems 배열에는 1번 진열대부터 진열대 번호 순서대로 보석이름이 차례대로 저장되어 있습니다.
- gems 배열의 각 원소는 길이가 1 이상 10 이하인 알파벳 대문자로만 구성된 문자열입니다.
여러가지 방법을 생각해 봤고, 시도를 해 보았지만 효율성에서 시간초과가 나서 결국 다른 분들의 블로그를 보고 공부했다. 효율성을 만족하기가 너무 어려웠다.
Github Link : https://github.com/yuseon27/Algorithm_Practice/blob/master/Kakao/2020_internship/03.%20jewerly_shopping.py
yuseon27/Algorithm_Practice
알고리즘 문제 풀이. Contribute to yuseon27/Algorithm_Practice development by creating an account on GitHub.
github.com
1. 투포인터 사용 - 드디어 효율성을 통과했다.
이 풀이에서 dictionary에 key에는 보석의 종류, value에는 해당 범위에서의 보석의 개수를 저장한다.
r_idx는 gems를 돌면서 dictionary에 보석을 추가하는 역할, l_idx는 gems를 돌면서 dictionary에서 보석을 제거하는 역할을 한다.
dictionary에 있는 보석의 개수가 주어진 보석의 종류의 개수와 다르면, r_idx를 증가시켜 dictionary에 해당 보석의 개수를 증가시킨다.
dictionary에 있는 보석의 개수가 주어진 보석의 종류의 개수와 같으면, answer의 한 후보가 되어 저장한다(해당 범위의 길이, [해당 범위의 시작 인덱스, 끝 인덱스]). 그리고 l_idx를 증가시켜 보석을 하나씩 빼 본다. 만약에 l_idx에 있는 보석이 dictionary에 0개가 있다면 해당 보석은 dictionary에서 삭제.
def solution(gems) : #{
answer = [0, len(gems)-1]
len_set_gems = len(set(gems)) ## 보색의 종류의 개수
len_gems = len(gems) ## 총 보석의 길이
gems_dict = {gems[0]:1} ## 현재 카트에 담긴 보석의 종류와 각 개수
end, start = 0, 0 ## end : 보석 하나씩 추가, start : 보석 하나씩 제거
while (end < len_gems and start < len_gems) : #{
if len(gems_dict) < len_set_gems : #{ ## dictionary에 모든 값이 아직 들어오지 않은 경우
end += 1
if end == len_gems : break ## 더 이상 보석을 추가할 수 없으면 멈춤
gems_dict[gems[end]] = gems_dict.get(gems[end], 0) + 1 ## 보석의 종류에 해당하는 개수 1 증가
#}
else : #{ ## dictionary에 모든 값이 들어온 경우
if end - start < answer[1] - answer[0] : ## 기존 값보다 작으면, [시작, 끝인덱스] 저장
answer = [start, end]
if gems_dict[gems[start]] == 1 : del(gems_dict[gems[start]]) ## 해당 보석의 개수가 1개이면 dictionary에서 삭제
else : gems_dict[gems[start]] -= 1 ## 해당 보석 빼보기
start += 1
#}
#}
return [answer[0]+1, answer[1]+1]
#}
2. Map에 인덱스 저장 - 효율성에서 3문제가 시간초과..ㅠ
이 풀이에서 dictionary에 key에는 보석의 종류, value에는 해당 보석의 인덱스를 저장한다.
보석을 돌면서 dictionary에 보석의 인덱스를 저장한다. 이 때, 이미 dictionary에 보석이 있으면 값을 삭제하고, 다시 dictionary에 넣어주는 작업을 한다. 이렇게 하면 나중에 dictionary에 있는 values만 뽑을 때 정렬된 순서로 뽑아, 최댓값 최솟값을 구하기 편하다.
dictionary에 있는 보석의 수와 주어진 보석의 종류가 같으면, 시작 인덱스와 끝 인덱스(values의 최솟값, 최댓값)을 가져와 예비 정답과 비교하여 길이가 더 짧은 것을 answer로 저장한다.
혹시 시간을 더 줄일 수 있는 방법을 아신다면 댓글로 남겨주시면 감사해용😊
def solution(gems):
answer = [1, len(gems)]
len_gems = len(set(gems))
gems_dict = {}
for idx, g in enumerate(gems) : #{
if g in gems_dict : del(gems_dict[g]) ## 있으면 삭제
gems_dict[g] = idx ## dictionary에 추가
if len(gems_dict.keys()) == len_gems : #{
## dictionary에 모든 값이 있으면, 최댓값과 최솟값을 구해서 길이가 더 짧은 경우 answer에 저장
min_idx = list(gems_dict.values())[0]+1
max_idx = list(gems_dict.values())[-1]+1
if max_idx - min_idx < answer[1] - answer[0] :
answer = [min_idx, max_idx]
#}
#}
return answer
- 참고한 자료