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

🤔 문제

---

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

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

😀 풀이

---

이 문제는 투 포인터를 이용하여 풀이하였습니다. 배열의 크기가 100,000으로 상당히 큰 편이고 이를 고려했을 때 시간 복잡도가 작은 자료구조를 써볼까, DP를 써볼까 등등이 머리를 스쳐갔지만 문제 상황 자체가 조건에 맞는 왼쪽 진열대 인덱스와 오른쪽 진열대 인덱스를 찾는 것이므로 투 포인터를 사용하면서 적절한 자료구조를 쓰면 문제 풀이가 가능하겠다고 생각했습니다. 

 

우선 코드를 작성하기 전 사고 과정은 아래와 같습니다.

1. 왼쪽 포인터와 오른쪽 포인터 사이에 있는 보석이 전체 보석 종류를 다 담는지 체크할 수 있어야겠다.
2. 종류를 다 담는다면 그것이 가장 짧은 구간인지 체크해야겠다. ➔ 포인터를 적절히 옮겨가며 답을 갱신해야겠다.
3. 가장 짧은 구간이라면 왼쪽 포인터가 더 작은게 리턴될 수 있게 해야겠다.

 

1번을 구현한 방식과 구현 중 고려했던 사항은 아래와 같습니다.

1. gems 배열을 set으로 변환하여 보석 종류만을 체크해야겠다.
2. 왼쪽 포인터와 오른쪽 포인터 사이에 어떤 보석들이 있는지 체크해야겠다.
➔ 포인터 사이에 값들을 배열로 관리하면 효율성이 떨어질 수 있으니 dict를 사용해 체크해주어야겠다.
4. dict의 key값 개수와 set(gem) 의 길이를 비교하면 보석 종류가 다 들어가 있는지 확인할 수 있겠다.

 

2번을 구현한 방식은 아래와 같습니다.

1. 기본적으로 오른쪽 포인터를 하나 늘릴 때마다 왼쪽 포인터는 얼마나 당겨올 수 있는지 확인하자.
2. 왼쪽 포인터를 땡겼을 때 dict의 보석 종류가 줄면 안 되므로 왼쪽 포인터가 가리키는 value에 대해 dict[value] > 1 인 경우에만 왼쪽 포인터를 당겨오자. ( 풀이 코드에 setStartPointer 함수로 구현 )
3. 왼쪽 포인터와 오른쪽 포인터 사이에 값들이 보석 종류를 모두 포함하고 이전에 구한 답보다 짧은 구간이라면 답을 갱신하자.

 

3번을 구현한 방식은 풀이 코드 25번 라인의 if 문 두 번째 조건을 고려해주면 중복 정답을 문제 조건에 맞게 처리해 줄 수 있습니다!

 

💻 풀이 코드는 아래와 같습니다.

def dictAdd(dict, value):
    if value in dict:
        dict[value] += 1
    else:
        dict[value] = 1
        
def setStartPointer(start, dict, gems):
    while 1:
        if dict[gems[start]] > 1:
            dict[gems[start]] -= 1
            start += 1
        else:
            return start   

def solution(gems):
    kinds = len(set(gems))
    length = len(gems)
    answer = [0, 1000002]
    dic = dict()
    start, end = 0, 0
    dictAdd(dic, gems[0])
    
    while 1:
        start = setStartPointer(start, dic, gems)
        if len(dic) == kinds and (end - start) < (answer[1] - answer[0]):
            answer = [start + 1, end + 1]
        end += 1
        if end == length:
            return answer
        dictAdd(dic, gems[end])
        
    return [start + 1, end + 1]

 

- 효율성 테스트 결과 -

테스트 1 〉	통과 (3.36ms, 10.3MB)
테스트 2 〉	통과 (5.04ms, 10.5MB)
테스트 3 〉	통과 (9.20ms, 11.1MB)
테스트 4 〉	통과 (9.85ms, 11.9MB)
테스트 5 〉	통과 (15.35ms, 12MB)
테스트 6 〉	통과 (20.29ms, 12MB)
테스트 7 〉	통과 (24.26ms, 12.8MB)
테스트 8 〉	통과 (27.48ms, 12.9MB)
테스트 9 〉	통과 (30.98ms, 13.4MB)
테스트 10 〉	통과 (35.45ms, 13.7MB)
테스트 11 〉	통과 (41.91ms, 14.5MB)
테스트 12 〉	통과 (31.41ms, 15.5MB)
테스트 13 〉	통과 (42.90ms, 16.1MB)
테스트 14 〉	통과 (62.38ms, 17.1MB)
테스트 15 〉	통과 (60.30ms, 17.8MB)