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

문제

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

프로그래머스

문제에서 요구하는대로 알고리즘을 구현하는 것 자체는 어렵지 않은 문제이지만, 제한 사항(시간/메모리)를 고려해

알고리즘을 구현하는 것이 까다로운 유형의 문제이다.

 

주어진 `gems`의 최대 길이가 100,000이기 때문에 이중 for 문을 사용해 전체 `gems`를 탐색하게 된다면 $O(e^{10})$의 복잡도가 요구되어 시간 초과가 발생할 것이 자명하므로, 탐색 수를 최소화하면서 문제에서 요구하는 바를 수행하는 것이 중요하다

풀이

풀이 1 (나의 풀이)

우선 $O(N^2)$의 알고리즘을 만들지 않기 위해서, [`start`,`end`] 두개의 index를 가지고 다음과 같은 단계를 수행하면서

전체 리스트(`gems`)의 탐색을 수행한다.

1. `start = 0`, `end = 0` / `start ~ end`까지의 보석을 담고 있는 dictionary `gem_dict`를 선언
2. `end`를 하나씩 늘려가며 `gem_dict`를 업데이트
3. `gem_dict`의 key와 전체 보석 종류가 동일하다면
   1. 규칙에 맞춰('구간의 길이가 짧은 경우' or '구간의 길이는 같지만 시작점이 빠른 경우') 정답을 업데이트
   2. 3의 조건에 부합하는 선에서 `start`를 늘려가며 `gem_dict`를 업데이트(`start ~ end`에 포함되지 않는 보석 제거)
   3. 3의 조건에 부합하지 않는다면, `start`를 늘리는 것을 멈추고 다시 2번 이후의 과정 반복

다음과 같은 `gems`가 있다고 하자,

1	2	3	4	5	6	7	8	9
A	A	A	B	B	C	C	B	A
`start` `end`

위의 알고리즘을 따라서 수행하게 되면, `start=1, end=6`일 경우에 처음 3번 조건에 부합하므로 정답을 [1,6]으로 업데이트 하게된다.

1	2	3	4	5	6	7	8	9
A	A	A	B	B	C	C	B	A
`start`					`end`

이후에는 3.1 ~ 3.3의 과정을 수행하면서 정답을 [3,6]까지 업데이트하고, [4,6]에서 3번 조건에서 빠져나와 2번 이후를 다시 수행한다.

1	2	3	4	5	6	7	8	9
A	A	A	B	B	C	C	B	A
			`start`		`end`

알고리즘 수행의 결과로 [4,9]에서 다시 3번 조건에 걸리게 되고, 그 이후로 3.1 ~ 3.3을 수행하면서 정답은 [7,9]로 업데이트된다.

1	2	3	4	5	6	7	8	9
A	A	A	B	B	C	C	B	A
						`start`		`end`

그 이후로 end를 늘릴 수 없기 때문에 알고리즘이 종료되고 최종 정답은 [7,9]로 마무리 된다.

소스 코드

def solution(gems):
    answer = [0,1e9]
    start,end = 0,0
    gem_dict = dict()
    nunique = len(set(gems))
    while start<len(gems) and end<len(gems):
        gem = gems[end]
        gem_dict[gem] = gem_dict.get(gem,0)+1

        if len(gem_dict)==nunique:
            if end-start<answer[1]-answer[0]:
                answer = [start+1, end+1]
            elif start<answer[0]:
                answer = [start+1, end+1]
                
            for i in range(start,end+1):
                gem = gems[i]
                gem_dict[gem]-=1
                
                if gem_dict[gem]==0:
                    del gem_dict[gem]
                    start=i+1
                    break
                else:
                    
                    if end-(i+1)<answer[1]-answer[0]:
                        answer = [i+2, end+1]
                    elif i+1<answer[0]:
                        answer = [i+2, end+1]
            
        end+=1
        
    return answer

다른 풀이

def solution(gems):
    gem_dict = dict()
    nunique = len(set(gems))
    answer = [1,1e9]
    start, end = 1,len(gems)
    for idx,gem in enumerate(gems):
        gem_dict[gem] = idx+1
        # start에 해당하는 Gem과 새로 업데이트될 gem이 같은 경우에, start 업데이트
        if gem==gems[start-1]:
            start = min(gem_dict.values())
        # 모든 종류를 포함하는 시점부터, end 업데이트
        if len(gem_dict)==nunique:
            end = idx+1
            # 정답 조건 확인 후, 업데이트
            if end-start<answer[1]-answer[0]:
                answer = [start, end]
            elif start<answer[0]:
                answer = [start, end]
        
            

    return answer

'풀이 1'의 원리와 비슷한 알고리즘이지만 조금 더 깔끔하다.

 

`gems`를 순회하면서 dictionary의 key가 모든 보석의 종류를 포함할 경우, 그 시점의 `start`와 `end`를 answer과 비교해 answer를 업데이트한다.

 

여기서 신경써야할 점은, `end`값은 dictionary내의 최대 value를 의미하므로 순회를 하면서 자동으로 업데이트가 진행되지만

`start`의 값은 최소 value값을 사용해야하므로 매 순회시마다 전체 dictionary를 탐색해 최소값을 계산하는 것은 상당한 소요가 발생한다

 

따라서, `start`가 업데이트 돼야하는 시점인, 새로운 `gem`이 기존의 `start`가 가리키는 `gem`과 일치할 경우, 즉 기존 `gem`의 index가 업데이트 되는 시점에만 최소값을 찾아 `start`를 업데이트 시켜야 한다.