(Python) - 프로그래머스(2020 카카오 인턴십) : 보석 쇼핑

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

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

우선, 분류를 구현 문제로 하였지만 사실 투 포인터 문제이다. 이 한 문제 때문에 카테고리를 새로 만들기가 좀 그래서 우선 구현에 넣어두었다. 추후 투 포인터 개념의 문제들을 더 풀게 된다면 카테고리를 옮기도록 하겠다.

 

• 해설 :

보석들의 이름이 담겨있는 배열이 주어질 때, 모든 보석의 종류들을 포함하는 가장 짧은 구간을 찾는 문제이다.

 

 

 

 

• 풀이 :

문제 설명은 간단하지만 투 포인터의 개념을 모른다면 쉽지 않은 문제이다. 우선, 모든 구간에 대해 구간마다 보석의 종류를 모두 포함하는지 찾는 방법은 보석의 최대 종류가 100,000개이므로 무조건 시간초과에 걸린다. 

 

투 포인터의 개념을 사용하면 시간초과에 걸리지 않고 해결할 수 있다. 알고리즘의 흐름은 다음과 같다.

 

1. end를 1씩 증가시키며 dictionary에 보석의 종류들을 넣고 dic의 key값 개수가 보석의 종류의 개수와 같아질 때까지 반복한다. 

 

2. 보석의 종류가 1개 줄어들어 모든 보석을 포함히지 않게 될 때까지 start를 1씩 증가시켜 최소 구간을 찾는다. 

 

3. 최소 구간을 찾았다면 이를 정답 배열에 넣고 현재 start와 end의 위치에서 1번으로 되돌아간다.

 

4. 모든 종류의 보석을 포함하는 구간들이 담겨있는 answer 배열을 구간이 짧고 (end-start)의 오름차순, 또한 start가 낮은 순으로 정렬하여 첫 번째 인덱스를 리턴하면 된다.

 

 

 

 

def solution(gems):
    answer = []
    l1 = len(gems)
    l = len(set(gems))
    dic = dict()
    start = 0
    end = 0
 
    check = []
 
    while True:
        c = len(dic)
        if start == l1:
            break
 
        if c == l:
            dic[gems[start]] -= 1
            if dic[gems[start]] == 0:
                del dic[gems[start]]
                answer.append([start+1,end])
            start += 1
            continue
        if end == l1:
            break
        if c < l:
            if gems[end] in dic:
                dic[gems[end]] += 1
            else:
                dic[gems[end]] = 1
            end += 1
 
    return sorted(answer,key = lambda x : (x[1]-x[0],x[0]))[0]