프로그래머스 보석 쇼핑 풀이: 해시 슬라이딩 윈도우

작성·코드 검증: solve together · 작성 언어: Python

0. 문제 링크와 출처

• 문제: 보석 쇼핑
• 출처: 프로그래머스, 2020 카카오 인턴십
• 자체 판단 난이도: Level 3

모든 보석 종류를 포함하는 구간 중 가장 짧은 구간을 찾아야 하고, 보석이 최대 100,000개라 모든 구간을 비교할 수 없다. 현재 윈도우의 종류별 개수를 관리하며 양끝을 이동하는 슬라이딩 윈도우와 해시를 함께 사용해야 하므로 Level 3으로 판단한다.

1. 문제 요약

진열대 번호 순서대로 보석 이름이 담긴 gems가 주어진다. 모든 종류의 보석을 최소 한 개씩 포함하는 가장 짧은 연속 구간을 찾아 [시작 번호, 끝 번호]로 반환해야 한다.

가장 짧은 구간이 여러 개라면 시작 번호가 작은 구간을 선택한다. 진열대 번호는 배열 인덱스가 아니라 1번부터 시작한다.

예를 들어 다음 배열에서는 3번부터 7번까지가 모든 종류를 포함하는 최소 구간이다.

[DIA, RUBY, RUBY, DIA, DIA, EMERALD, SAPPHIRE, DIA]

2. 문제 해결에 사용되는 알고리즘이나 자료구조 설명

구간 판정

두 포인터 left, right로 현재 연속 구간 [left, right]를 관리한다. right를 오른쪽으로 한 칸씩 이동하며 보석을 구간에 추가하고, 해시 맵 counts에 구간 안의 보석별 개수를 저장한다.

현재 구간에 들어 있는 보석 종류 수가 전체 종류 수와 같아지면 모든 종류를 포함한 상태다. 이때 left를 오른쪽으로 이동하면서 여전히 모든 종류가 남아 있는 동안 구간을 줄인다. 더 이상 줄일 수 없는 순간의 구간이 현재 right에서 가능한 가장 짧은 구간이다.

보석이 모두 갖춰진 뒤 왼쪽을 줄이는 과정

right를 늘려 모든 종류를 확보한 뒤에는 왼쪽의 중복 보석을 제거해 구간을 줄인다. 어떤 종류의 개수가 1에서 0으로 바뀌면 그 순간 구간이 무효가 되므로, 마지막으로 유효했던 구간을 후보로 기록하고 오른쪽을 다시 확장한다.

공식 예제에서 right = 6일 때 처음 모든 종류가 모인 구간은 [0, 6]이다. 왼쪽부터 보석을 빼면 다음 상태가 된다.

따라서 이 right에서 가장 짧은 유효 구간은 [2, 6], 즉 진열대 번호 [3, 7]이다. 불변식은 counts가 현재 구간 안의 실제 개수만 담고, 모든 종류가 포함될 때 왼쪽 경계를 더 줄일 수 없다는 것이다. 각 포인터는 한 방향으로만 최대 한 번 지나므로 전체는 O(n)이다.

오답 접근과 반례

모든 시작점과 끝점을 조합해 구간마다 보석 종류를 세면 O(n^2) 이상의 시간이 필요하다. 보석이 100,000개일 때 불필요한 구간을 대부분 반복해서 확인하게 된다.

모든 종류를 포함한 순간 바로 결과를 저장하고 left를 줄이지 않으면 최소 구간을 놓칠 수 있다.

gems = [A, B, A, C]

[A, B, A, C]도 모든 종류를 포함하지만, 왼쪽의 중복 A를 제거하면 [B, A, C]로 더 짧아진다. 유효한 동안 왼쪽을 계속 줄여야 한다.

길이가 같은 후보가 여러 개일 때 갱신 조건을 길이만 비교하면 시작 번호 우선 조건을 놓칠 수 있다. 따라서 길이가 같을 때는 더 작은 left를 선택한다.

시간·공간 복잡도

두 포인터가 각각 오른쪽으로만 이동하므로 시간 복잡도는 O(n)이다. 현재 구간의 보석 개수를 저장하는 해시 맵은 보석 종류 수에 비례하므로 공간 복잡도는 O(k)이고, k는 서로 다른 보석 종류의 수다.

3. 문제 해결 코드 (Python)

def solution(gems):
    total_types = len(set(gems))
    counts = {}
    left = 0
    best_left = 0
    best_right = len(gems) - 1

    for right, gem in enumerate(gems):
        counts[gem] = counts.get(gem, 0) + 1

        while len(counts) == total_types:
            current_length = right - left
            best_length = best_right - best_left

            if current_length < best_length or (
                current_length == best_length and left < best_left
            ):
                best_left = left
                best_right = right

            counts[gems[left]] -= 1
            if counts[gems[left]] == 0:
                del counts[gems[left]]
            left += 1

    return [best_left + 1, best_right + 1]

구간 길이는 양끝을 포함한 원소 개수인 right - left + 1로 비교해도 되지만, 모든 후보에 1이 공통이므로 right - left를 비교해도 결과는 같다. 반환할 때는 문제의 1번 진열대 기준에 맞춰 양쪽 인덱스에 1을 더한다.

복사해 실행할 테스트

아래 검사를 풀이 코드 아래에 붙여 python 파일명.py로 실행하면 최소 구간과 시작 위치 동률 조건을 확인할 수 있다.

assert solution(["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"]) == [3, 7]
assert solution(["AA", "AB", "AC", "AA", "AC"]) == [1, 3]

4. 공식 예제와 추가 검증

공식 예제와 단일 종류, 같은 길이 후보의 시작 위치 우선 조건을 Python 코드로 실행했다.

공식 예제

추가 검증 1: 같은 길이 후보의 시작 위치 비교

입력: gems = ["A", "B", "A", "C", "B", "C"]
기대 출력: [2, 4]
확인 결과: 통과
검증 목적: 모든 종류를 포함하는 최소 길이 후보 중 시작 위치가 가장 작은 구간 선택 확인

5. 다른 풀이 방식 검색 및 비교

• 프로그래머스 공식 문제는 모든 보석 종류를 포함하는 가장 짧은 연속 구간과 시작 위치 우선 조건을 정의한다.
• 프로그래머스 보석 쇼핑 참고 풀이는 투 포인터와 현재 윈도우의 보석 개수를 이용해 구간을 줄이는 접근을 설명한다.

모든 구간을 확인하는 완전탐색은 입력 크기 때문에 사용할 수 없다. 정렬이나 이분 탐색으로 보석 종류를 처리하는 방식보다, 원래 진열 순서를 유지한 채 right를 확장하고 left를 축소하는 슬라이딩 윈도우가 이 문제의 연속 구간 조건에 직접 맞는다.

마무리

보석 쇼핑은 모든 종류를 포함한다는 조건을 해시 개수로 표현하고, 조건을 만족할 때마다 왼쪽을 줄여 최소 구간을 찾는 슬라이딩 윈도우 문제다. 각 포인터가 한 번씩만 이동하고 동률일 때 시작 위치까지 비교하면 O(n) 시간에 정확한 진열대 구간을 반환할 수 있다.