[프로그래머스/Java] Lv.3 - 보석 쇼핑

승래·2026년 3월 31일

프로그래머스 Lv.3 - 보석 쇼핑

요구사항

모든 종류의 보석을 하나 이상 포함하는 가장 짧은 구간을 구하는 문제
구간의 시작과 끝 인덱스를 반환 (1-indexed)
구간 길이가 같으면 시작 인덱스가 작은 것을 반환

접근 방식

투포인터 + HashMap 으로 풀었다.

핵심 아이디어

lt, rt 두 포인터로 구간을 관리
Map<보석이름, 개수>로 현재 구간의 보석 개수 관리

map.size() == 전체 보석 종류 수 → 모든 보석 포함 ✅

모든 보석 포함 안 됨 → rt 확장
모든 보석 포함 됨 → 최소 구간 갱신 후 lt 축소

왜 List.contains() 대신 Map을 써야 하는가?

List.contains() → O(n) → 전체 O(n²) → 시간초과!
map.size() 비교 → O(1) → 전체 O(n) → 통과!

Map에서 보석 제거 시 주의사항

// Map 순회 중 삭제하면 ConcurrentModificationException 발생!
// lt 이동할 때 바로 제거
map.put(gems[lt], map.get(gems[lt]) - 1);
if(map.get(gems[lt]) == 0) map.remove(gems[lt]); // 0이 되면 즉시 제거

코드

import java.util.*;

class Solution {
    public int[] solution(String[] gems) {
        int kind = (int) Arrays.stream(gems).distinct().count();

        int lt = 0, rt = 1, n = gems.length;
        int start = 0, end = 1;
        int dist = Integer.MAX_VALUE;

        Map<String, Integer> map = new HashMap<>();
        map.put(gems[0], 1);

        while (lt <= rt) {
            if (map.size() != kind) {
                if (rt >= n) break;
                map.put(gems[rt], map.getOrDefault(gems[rt], 0) + 1);
                rt++;
            } else {
                if (dist > rt - lt) {
                    dist = rt - lt;
                    start = lt;
                    end = rt;
                }
                map.put(gems[lt], map.get(gems[lt]) - 1);
                if (map.get(gems[lt]) == 0) map.remove(gems[lt]);
                lt++;
            }
        }

        return new int[]{start+1, end};
    }
}