[프로그래머스] Python - 보석 쇼핑

https://programmers.co.kr/learn/courses/30/lessons/67258

코딩테스트 연습 - 보석 쇼핑

생각

어렵게 생각하면 어렵고 쉽게 생각하면 쉬운 문제였습니다.. 완전탐색으로 가능한 모든 구간을 찾아야 하는 줄 알았는데 투포인터+딕셔너리 자료구조로 풀면 되는 문제였습니다.

 

tech.kakao.com/2020/07/01/2020-internship-test/ 해설을 참고하여 풀었습니다.

 

1. 보석의 종류별 갯수를 카운트 할 수 있게 딕셔너리를 만듭니다.

2. start, end 인덱스를 만듭니다.

3. 투 포인터의 범위가 진열대의 범위를 벗어나면 종료시켜줍니다.

4. 아직 보석을 다 못샀다면 end 인덱스를 증가시켜줍니다. end의 범위를 체크해줍니다. end를 증가시켜줬으므로 보석의 카운트도 늘려줍니다.

5. 보석의 종류만큼 모두 샀다면 정답 배열에 (구간 길이, [시작번호, 끝번호]) 를 append 시켜줍니다. 그 다음 start 인덱스에 해당하는 보석을 한개 제거해주고 보석을 산 횟수가 0이라면 보석을 아예 제거해줍니다. 마지막으로 start인덱스를  1 증가시켜줍니다.

6. 정답의 후보가 되는 answer 배열에서 길이가 작은순 -> 시작인덱스가 작은순서로 정렬조건을 주어 정렬시킵니다. 그 다음 answer의 가장 첫번째 원소의 [시작인덱스, 끝인덱스] 정보를 리턴시켜줍니다

Python Code

from collections import defaultdict

def solution(gems):
    answer = [] # 길이, [시작인덱스, 끝인덱스]
    countGems = defaultdict(int)
    countGems[gems[0]]=1
    typeCnt = len(set(gems)) # 보석 종류 개수
    length = len(gems) # 진열대 길이

    start,end = 0,0
    while start < length and end < length:
        if len(countGems) < typeCnt: # 아직 보석 다 못삼
            end+=1 #오른쪽으로 이동
            if end == length: 
                break
            countGems[gems[end]]+=1 # 이동했으니깐 보석 빈도수 증가

        # 조건 만족함
        if len(countGems) == typeCnt:
            answer.append((end-start, [start+1, end+1]))

            #왼쪽빼주기
            countGems[gems[start]]-=1
            if countGems[gems[start]] == 0:
                del countGems[gems[start]]
            start += 1

    answer = sorted(answer, key=lambda x : (x[0], x[1])) # 길이가 같으면 인덱스가 작게
    return answer[0][1]