[알고리즘] 프로그래머스 보석 쇼핑 - Python

문제 : 프로그래머스 보석 쇼핑 문제

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

프로그래머스

문제를 봤을 때, 하나의 배열이 주어지고 이 배열을 탐색해 나가야 하기 때문에 이중 for문 혹은 투포인터로 해결할 수 있을거라고 생각했다. 그래서 두 가지 모두를 해보았다. 

 

먼저 이중 for문을 사용한 풀이이다.

def solution(gems):
    answer = []
    cnt=len(set(gems))
    min_len=len(gems)
    for i in range(len(gems)):
        dict={}
        for j in range(i,len(gems)):
            
            if gems[j] in dict:
                dict[gems[j]]+=1
            else:
                dict[gems[j]]=1
            if len(dict)==cnt :
                if min_len > j-i+1:
                    answer=[i+1,j+1]
                    min_len=j-i+1
                elif min_len==j-i+1 and len(answer)==0:
                    answer=[i+1,j+1]
            
    return answer

구현하기 전부터 시간 초과가 날 것 같다는 생각을 했는데 역시 시간초과가 났다. 그래도 풀이를 설명해보자면 먼저 cnt 값은 중복을 제거한 보석의 개수, min_len는 보석 배열의 길이이고 이 변수에 가장 짧은 구간의 길이를 저장한다. 

 

for문을 돌면서 매번 새로 set을 선언해서 중복을 제거한 보석의 개수를 셀 수도 있지만, 이렇게 하면 효율성이 더 떨어지기에 dict라는 dictionary를 하나 선언했다. 여기에 i와 j를 변화하면서 보석을 하나씩 추가해나가며 dict의 길이로 중복을 제거한 보석 개수를 판단했다. 이 풀이로는 테스트 케이스는 모두 통과를 했지만, 효율성 테스트에서 모두 시간초과가 났기 때문에 효율이 낮다고 생각하여 투포인터로 넘어갔다.

 

투포인터를 활용하여 문제를 푸는 과정에서 시간이 꽤 소요되었다. 먼저 처음 투포인터로 작성한 코드이다.

def solution(gems):
    answer = []
    l,r=0,0
    cnt=len(set(gems))
    dict={}
    part=gems[0:1]
    for i in part:
        if i in dict:
            dict[i]+=1
        else:
            dict[i]=1
    while l<=r:
        if len(dict)==cnt:
            l+=1
            dict[gems[l-1]]-=1
            if dict[gems[l-1]]==0: 
                del dict[gems[l-1]]
                return [l, r+1]
        else:
            r+=1
            if gems[r] in dict:
                dict[gems[r]]+=1
            else:
                dict[gems[r]]=1
        
        
    return answer

 

나름 투포인터를 활용해서 다양한 엣지케이스도 반영했다고 생각했는데, 시간초과는 나지 않지만, 여러 테스트 케이스를 통과하지 못했다. 그래서 테스트 케이스를 추가해가며 예외 상황을 찾아나갔다.

 

먼저 가장 크게 문제가 된 상황은 "가장 짧은 구간"을 반환해야한다는 점이다. 이 코드에서는 가장 짧은지 여부는 검토하지 않고, 첫 인덱스부터 중복을 제거한 보석의 개수가 전체 보석의 종류와 같기만 하면 바로 return을 해버렸다. 이 상황을 검증할 수 있는 테스트 케이스는 다음과 같다. 

 

이 두가지 경우에서 통과를 하기 위해서는 바로 return을 해버리는 부분의 코드를 수정할 필요가 있었다. 

 

def solution(gems):
    answer = []
    l,r=0,0
    cnt=len(set(gems))
    dict={}
    min_len=len(gems)+1
    part=gems[0:1]
    for i in part:
        if i in dict:
            dict[i]+=1
        else:
            dict[i]=1
    while r<len(gems):
        if len(dict)==cnt:
            if min_len > r-l+1:
                answer=[l+1, r+1]
                min_len=r-l+1
                
            l+=1
            dict[gems[l-1]]-=1
            if dict[gems[l-1]]==0: 
                del dict[gems[l-1]]
        else:
            r+=1
            if r<len(gems):
                if gems[r] in dict:
                    dict[gems[r]]+=1
                else:
                    dict[gems[r]]=1
        
    return answer

 

수정된 부분이 조금씩 있다. 먼저 min_len 값을 추가했다. 이 변수를 사용하면 조건을 만족하는 구간 중 가장 짧은 구간의 길이를 저장할 수 있다. 그리고 while문의 조건도 수정했다. 기존에는 l<=r 이면 r이 배열의 밖으로 나가는 경우를 막을 수 없기에 r<len(gems)로 수정을 해주고, while문 안에서도 조건을 추가해주었다. 또한, min_len로 구간의 길이를 기록해두면서 배열의 끝까지 검사할 수 있도록 했다.

 

이렇게 한 결과, 테스트 케이스와 효율성 테스트를 모두 만족할 수 있었다. 

 

또 한번 느낀 점은 투포인터를 구현할 때는 인덱스가 범위 안에 있는지 검증하는게 중요하다는 것과, 문제를 꼼꼼히 읽는 것이 중요하다는 점이다.