프로그래머스 - 보석 쇼핑 with.Python

오늘은 프로그래머스에 보석 쇼핑 문제를 풀어봤습니다. 하지만 결국 풀지 못해서 GPT의 힘을 빌렸네요.. 허허
그래서 다시 한번 풀이를 생각해보고 되짚어볼겸 블로그에 남기려고 합니다.

1. 문제 설명

1-1. 제한사항

• gems 배열의 크기는 1 이상 100,000 이하입니다.
  • gems 배열의 각 원소는 진열대에 나열된 보석을 나타냅니다.
  • gems 배열에는 1번 진열대부터 진열대 번호 순서대로 보석이름이 차례대로 저장되어 있습니다.
  • gems 배열의 각 원소는 길이가 1 이상 10 이하인 알파벳 대문자로만 구성된 문자열입니다.

---

2. 나의 풀이 방법(실패)

딕셔너리를 활용해 각 종류를 key로 설정하고 value에 key에 해당하는 인덱스를 넣어서 맵핑을 했다.
그러고 각 key에서 값들을 하나씩 뽑고 인덱스간 빈 자리가 가장 적게 만들려고 했다. 하지만 실패..

---

3. GPT의 풀이 방법

 def solution(gems):
    gem_types = len(set(gems))  # 보석 종류 개수
    gem_count = {}                # 현재 구간 내 보석의 개수를 담는 딕셔너리
    answer = [0, len(gems)]     # 초기 구간은 가장 긴 구간으로 설정
    start, end = 0, 0            # 슬라이딩 윈도우 포인터

    while end < len(gems):
        # 오른쪽 포인터 확장
        gem = gems[end]
        # 딕셔너리에 해당 보석이 있으면 +1, 없으면 0에서 시작해서 +1
        gem_count[gem] = gem_count.get(gem, 0) + 1
        end += 1

        # 현재 구간에 모든 종류가 포함되면 왼쪽 포인터 줄이기
        while len(gem_count) == gem_types:
            # 더 짧은 구간이면 정답 갱신
            if end - start < answer[1] - answer[0]:
                answer = [start, end]

            # 왼쪽 포인터 줄이기 전 보석 제거
            gem_count[gems[start]] -= 1
            if gem_count[gems[start]] == 0:
                del gem_count[gems[start]]
            start += 1

    return [answer[0] + 1, answer[1]]

3-1. 사용한 알고리즘 기법

슬라이딩 윈도우 : 두 포인터로 구간을 움직이며 조건을 만족하는 가장 짧은 구간을 찾는 기법
해시맵(dict) : 현재 구간에 어떤 보석이 몇 개 있는지 빠르게 체크

3-1-1. end 포인터를 오른쪽으로 계속 이동하면서 보석을 추가

while end < len(gems):
    gem = gems[end]
    gem_count[gem] = gem_count.get(gem, 0) + 1
    end += 1

• end 위치의 보석을 카운트
• 해당 보석이 처음 등장하면 gem_count의 키가 추가됨

3-1-2. 모든 보석 종류가 구간 안에 다 들어왔따면, start를 이동시켜서 구간을 줄여봄

while len(gem_count) == gem_types:

• 현재 구간이 모든 보석 종류를 포함하고 있다면
• 가능한 start를 오른쪽으로 이동시켜서 구간을 최소화

3-1-3. 구간 길이가 최소일 경우 answer 갱신

if end - start < answer[1] - answer[0]:
    answer = [start, end]

• 현재 구간이 이전에 저장한 정답보다 더 짧다면 answer 업데이트

3-1-4. start를 한 칸 이동시키기 전, 해당 보석 개수를 줄임

gem_count[gems[start]] -= 1
if gem_count[gems[start]] == 0:
    del gem_count[gems[start]]
start += 1

• start 위치에 있는 보석 개수를 1개 줄임
• 만약 그 보석의 개수가 0이 되면 딕셔너리에서 제거
• 그러면 gem_count에 들어있는 보석 종류 수가 줄어들고 while문 탈출

---

4. 시간복잡도

시간 복잡도는 전체 보석을 결국 탐색을 하기 때문에 O(N) 이다.

---

5. 몰랐던 내용

5-1. dict.get(key, default)

• 만약 key가 딕셔너리에 있으면 그 값을 반환
• 없다면 default 값을 반환