[프로그래머스] 보석 쇼핑 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

프로그래머스

 

1. 문제 설명

2. 풀이과정

해당 문제는 보석의 모든 종류를 포함하는 구간 중 가장 짧은 구간을 구하는 문제이다.

해당 문제에서는 시작부터 끝까지 구간의 끝을 늘려가면서 딕셔너리를 활용해 각 보석의 개수를 저장하고 딕셔너리의 보석의 종류가 전체 구매할 보석의 종류와 일치하면 현재 구간에서 가능한 모든 구간을 구한다.

가능한 모든 구간을 구했다면 구간의 길이가 짧은 순서대로 정렬하여 가장 짧은 구간을 찾는다.

 

1. 보석의 종류를 저장한다. num = len(set(gems))
2. 가능한 구간을 저장할 리스트를 생성한다. result = list()
3. 구간의 시작 위치를 저장할 변수를 생성하고 초기화한다. start = 0
4. 각 보석의 개수를 저장할 딕셔너리를 생성한다. d = {}
5. 구간의 끝 위치를 하나씩 지정하며 for end in range(len(gems))
6. 만약 해당 보석이 딕셔너리에 있으면 if (gems[end] in d)
7. 해당 보석의 개수를 증가시키고 d[gems[end]] += 1
8. 반면에 해당 보석이 처음 나온 보석이라면 else
9. 해당 보석을 딕셔너리에 추가한다. d[gems[end]] = 1
10. 딕셔너리에 있는 보석의 종류가 구매하여는 보석의 종류와 동일하면 반복한다. while (len(d) == num)
11. 가능한 구간 리스트에 해당 구간을 추가하는데, 이때 시작이 1부터이므로 인덱스 값으로 저장되어 있는 시작 위치와 마지막 위치는 1 증가시켜야 한다. result.append([start + 1, end + 1])
12. 구간을 좁히기 위해 구간의 시작 위치에 해당하는 보석을 하나 제거한다. d[gems[start]] -= 1
13. 만약 제거한 뒤 해당 보석의 개수가 0개이면 if (d[gems[start]] == 0)
14. 해당 보석을 딕셔너리에서 제거한다. del d[gems[start]]
15. 시작 위치를 증가시켜 구간을 좁혀준다. start += 1
16. 가능한 모든 구간을 구했다면 이를 구간의 길이가 짧은 순서대로 정렬한다. result.sort(key = lambda x : x[1] - x[0])
17. 가장 앞에 오는 구간이 가장 짧은 구간이므로 저장한다. answer = result[0]
    

반응형

3. 소스코드

def solution(gems):
    answer = []

    num = len(set(gems))
    result = list()

    start = 0
    d = {}
    for end in range(len(gems)):
        if (gems[end] in d):
            d[gems[end]] += 1
        else:
            d[gems[end]] = 1

        while (len(d) == num):
            result.append([start + 1, end + 1])
            
            d[gems[start]] -= 1
            
            if (d[gems[start]] == 0):
                del d[gems[start]]
                
            start += 1
    
    result.sort(key = lambda x : x[1] - x[0])
    answer = result[0]
    
    return answer