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

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

프로그래머스

 

내 코드

from collections import Counter

def solution(gems):
    answer = []
    end,start =0,0
    l = len(set(gems)) #진짜배기들
    gemcnt =Counter()
    
    while end < len(gems):
        while end < len(gems) and len(gemcnt) != l:
            
            if gems[end] in gemcnt:
                gemcnt[gems[end]] +=1
            else: 
                gemcnt[gems[end]] =1
            end +=1
        
        while start < len(gems) and len(gemcnt) == l:
            gemcnt[gems[start]] -=1
            if gemcnt[gems[start]] ==0:
                gemcnt.pop(gems[start])
            start +=1
            
        answer.append((end-start, start, end)) #짧은 거리를 구해야 하니까!!
    answer.sort()
                 
    return answer[0][1], answer[0][2]

 

코드 리뷰

투 포인터 알고리즘

이 문제는 전형적인 투포인터 문제지만, 수로 이루어진 게 아니라 보석 이름으로 이루어져 있기 때문에 dictionary를 사용하는 것이 편리하다. 그리고 내가 이 문제를 통해 Counter를 알게 되었는데, 정말 좋다..! 그러면 문제를 뜯어보자.

 

이 배열의 크기는 최대 100,000이다. 그래서 O(n^2) 이상인 탐색 알고리즘으로는 시간 초과가 발생한다. 따라서 투포인터 O(n) 로 풀어야 한다.

    answer = []
    end,start =0,0
    l = len(set(gems)) #진짜배기들
    gemcnt =Counter()

기본 세팅이다. 진열된 모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 구간을 찾아서 구매하는 것이 목적이다. 이를 위해서는 먼저 몇 가지의 종류가 있는지부터 파악해야 하고, 이를 알기 위한 코드가 len(set(gems))이다. 그리고 dict는 Counter로 대체했다. (Counter가 dict의 확장판이다)

 

while end < len(gems):
        while end < len(gems) and len(gemcnt) != l:
            
            if gems[end] in gemcnt:
                gemcnt[gems[end]] +=1
            else: 
                gemcnt[gems[end]] =1
            end +=1
        
        while start < len(gems) and len(gemcnt) == l:
            gemcnt[gems[start]] -=1
            if gemcnt[gems[start]] ==0:
                gemcnt.pop(gems[start])
            start +=1

그리고 투 포인터 알고리즘대로 풀이를 진행한다. 먼저 등장하는 while문은 총 보석의 개수보다 end가 작으면서, 보석의 종류 개수만큼 쌓이지 않았다면 반복하는 반복문이다. 역시나 dict를 사용할 때처럼 in 연산자를 사용하여, 이미 있다면 +=1, 없다면 =1 으로 값을 생성해준다.



그리고 다음 등장하는 while문은 보석 종류의 개수만큼 쌓였다면, 일단 value 값을 1씩 뺀다. 그렇게 해서 만약 value 값이 0이 된다면 필요없는 gem이라는 소리이니까, pop으로 없애버린다. 그리고 다시 start 값을 1 추가한다.

 

start	end
0	0
0	1
0	2
0	3
0	4
0	5
0	6
0	7
1	7
2	7
3	7

첫 번째 케이스의 경우 간단하게 나타내면 이 과정을 거친  후 [3, 7]이 나온다. 

한마디로 말하자면 처음에 모든 종류에 대한 정보를 다 수집했다가, 하나씩 빼면서 이거 빼도 괜찮은지 계속해서 검사하고, 필요없는 것들은 pop 하면서 start, end의 순서를 구한다. 투포인터 문제는 더 많이 접해볼 필요가 있는 것 같다.