2020 카카오 인턴십 보석 쇼핑
문제 링크
https://programmers.co.kr/learn/courses/30/lessons/67258?language=python3
전체 코드
def calculaterGap(x):
return x[1]-x[0]
def solution(gems):
answer = []
gems_cnt = len(set(gems))
gems_dict = dict()
i, j = 0, 0
gems_dict[gems[i]] = 1
while i < len(gems) and j < len(gems):
if len(gems_dict) < gems_cnt:
j += 1
if j >= len(gems):
break
gems_dict[gems[j]] = gems_dict.get(gems[j], 0) + 1
else:
answer.append([i+1, j+1])
if gems_dict[gems[i]] == 1:
del gems_dict[gems[i]]
else:
gems_dict[gems[i]] -= 1
i += 1
answer.sort(key=lambda x: calculaterGap(x))
return answer[0]코드 작성시 고민했던 점과 배운 점
- 자료구조와 알고리즘에 대한 고민
- 평소에 효율성 테스트가 포함된 문제를 풀 때, 다른 문제를 풀 때보다 자료구조와 알고리즘 선택에 있어 고민을 많이 한다. 해당 문제를 풀기 전에 단순 리스트에 투포인터를 적용하여 풀라고 햇으나 역시나 효율성을 뚫지 못했다. 딕셔너리 자료구조와 투포인터 알고리즘을 적용하여 문제를 해결하였다.
- 간단하게 투포인터 알고리즘을 설명하자면, 완전 탐색을 통한 문제 풀이시 시간 초과나는 문제를 해결하는 방안 중 하나이다. 1차원 배열에서 각자 다른 원소를 가르키는 2개의 포인터를 조작하여 원하는 것을 얻는 알고리즘이다.
- 투포인터 알고리즘을 통한 문제 풀이 (먼저 증가하는 j, 뒤따라 증가하는 i)
2.1 딕셔너리에 포함된 gems의 종류 갯수가 전체 종류 갯수보다 작을경우
if len(gems_dict) < gems_cnt:
j += 1
if j >= len(gems):
break
gems_dict[gems[j]] = gems_dict.get(gems[j], 0) + 1- 아직 딕셔너리내에 gems의 종류 갯수가 충분하지 않기 때문에 j를 증가시켜 gems을 딕셔너리에 추가한다.
- 딕셔너리의 get(key, '디폴트 값')은 딕셔너리 안에 찾으려는 key 값이 있으면 key 값을 가져오고, 없을 경우 디폴트 값을 대신 가져올 수 있다.
2.2 딕셔너리에 포함된 gems의 종류 갯수가 전체 종류 갯수와 동일할 경우
else:
answer.append([i+1, j+1])
if gems_dict[gems[i]] == 1:
del gems_dict[gems[i]]
else:
gems_dict[gems[i]] -= 1
i += 1- 딕셔너리내 포함된 gems의 종류가 전체의 종류라면, 이 때 범위(i+1,j+1)을 answer에 추가한다.
- i를 증가시키면서 i가 가리켰던 gem을 삭제한다.
- 결과 출력
def calculaterGap(x):
return x[1]-x[0]
생략...
answer.sort(key=lambda x: calculaterGap(x))
return answer[0]- 가장 짧은 구간을 구해야하기 때문에 구간의 간격을 구하는 calculaterGap() 함수를 정의하여, 이를 sort시 key에 lambda를 사용하여 정렬 기준을 설정했다.
결과
