[프로그래머스lv3] [2020 카카오 인턴십] 보석 쇼핑

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

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

---

풀이

 

gems에서 보석을 차례대로 반복문에 넣는다.

 

큐에 차례때로 보석을 넣어준다.

 

또한 보석의 수를 효율적으로 계산하기 위해 dict를 따로 만들어 요소의 수를 기록한다.

 

set을 통해 큐에 모든 보석이 들어갔는지 확인한다.

 

모든 요소가 들어갔다면

 

• 현재 상태를 저장한다. 나중에 답 비교를 위해 우선순위 큐에 [큐길이, 시작위치] 로 저장한다.
• 큐의 첫번째 보석의 수가 2 이상이라면 현재 큐를 한 번 pop를 해주고 해당 보석의 수를 dict에서 -1해준다.
• 남은 큐의 상태를 같은 형식으로 우선순위 큐에 저장한다.
• q의 첫번째 단어의 count를 다시 확인하며 위 과정을 반복한다.
• 첫 번째 단어의 count가 다시 1이 되었다면 종료하고 다시 for문으로 돌아온다.

위 과정을 거치면 우선순위 큐의 첫번째 요소에 가장 작은 큐길이 중 가장 작은 시작위치를 가진게 위치한다.(heapq 모듈은 최소힙이기 때문)

 

나는 큐로 삽입과 삭제를 통해 보석수를 카운트하고 시작위치와 길이를 계산했지만

카카오 풀이를 보면 투포인터를 이용했다. 투 포인터 풀이가 훨씬 깔끔하다.

 

---

시간복잡도

 

보석의 수가 N이라면 for문에서 N번 호출하기 때문에 O(N) 이다.

 

for문안에서 while문이 존재하지만 while문은 N개의 큐 중복없이 삭제,삽입 하기 때문에 총 횟수가 N번을 넘지 않는다. 따라서 O(N)을 넘지 않는다.

 

for문 안에서 우선순위 큐 연산이 매번 일어난다. 우선순위 큐의 삽입과 삭제는 O(logN)이다.

 

따라서 O(N) * O(logN) => O(Nlog(N)) 이라고 볼 수 있다.

 

---

코드

from collections import defaultdict,deque
import heapq

def solution(gems):
    gem_set,now_set = set(gems), set()
    gem_dict = defaultdict(int)
    pq = []
    q = deque([])
    for i,gem in enumerate(gems):
        now_set.add(gem)
        gem_dict[gem]+=1
        q.append((i+1,gem))

        if len(now_set) == len(gem_set): # q에 모든 요소가 있다
            idx = q[0][0]
            l = len(q)
            heapq.heappush(pq,[l,idx])

            while gem_dict.get(q[0][1]) >= 2: # q의 첫번째 요소가 q안에 2개 이상이라면 while 문 진행
                idx,g = q.popleft()
                l = len(q)
                heapq.heappush(pq,[l,idx+1])
                gem_dict[g] -= 1

    l,s = heapq.heappop(pq)

    return [s,s+l-1]