[DAY89] Algorithm : Jewelry Shopping

진열된 모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 구간을 찾는 문제다. 이중 반복문($O(N^2)$)은 시간 초과가 발생하므로, 투 포인터(Two Pointers) 알고리즘을 사용하여 $O(N)$의 시간 복잡도로 해결해야 한다.

---

❓ 문제 분석

• 목표: 모든 보석 종류를 포함하는 최소 길이의 구간 [start, end] 구하기.
• 제약 조건: gems 배열의 크기는 최대 100,000이다.
  • $O(N^2)$ 탐색 시 100억 번의 연산이 필요하여 시간 초과.
  • $O(N)$ 혹은 $O(N \log N)$으로 해결해야 함.
• 핵심 키워드: "모든 종류", "가장 짧은 구간", "연속된".

---

💡 풀이 설계

1. 자료구조 선택

• 목표 확인: unordered_set을 사용하여 중복 없는 보석의 총 종류 개수(Target)를 파악한다.
• 구간 관리: unordered_map<string, int>를 사용하여 현재 구간(start~end) 내에 각 보석이 몇 개씩 있는지 카운트한다.

2. 투 포인터 (Sliding Window) 전략

• 확장 (end 증가): end 포인터를 오른쪽으로 이동시키며 맵에 보석을 추가한다.
• 조건 확인: 맵의 사이즈(size())가 총 보석 종류 수와 같아지면, 현재 구간은 유효한 구간이다.
• 축소 (start 증가): 유효한 상태를 유지하면서 구간을 최대한 줄여야 한다.
  • start 위치의 보석이 구간 내에 2개 이상이라면? $\rightarrow$ 하나를 빼도 종류 수에는 변함이 없으므로 start를 오른쪽으로 당긴다. (중복 제거)
  • start 위치의 보석이 딱 1개라면? $\rightarrow$ 더 이상 당길 수 없으므로 멈춘다.
• 갱신: 축소가 끝난 시점의 길이를 측정하여 최솟값(min_len)을 갱신한다.

---

💻 코드 구현

#include <string>
#include <vector>
#include <unordered_map>
#include <unordered_set>

using namespace std;

vector<int> solution(vector<string> gems) {
    vector<int> answer = { 0, 0 };

    // 보석 종류 변수 (unordered_set)
    unordered_set<string> gem_set(gems.begin(), gems.end());

    // 변수 초기화
    int min_len = 100001; // 최소구간을 찾는 문제이므로 충분히 큰 값으로 초기화
    unordered_map<string, int> gem_map;
    int start = 0;
    int end = 0;

    // 투 포인터 (슬라이딩 윈도우)
    for (int end = 0; end < gems.size(); end++) {
        // 맵에 보석 추가
        gem_map[gems[end]]++;

        // 맵 사이즈가 전체 종류와 같다면?
        if (gem_map.size() == gem_set.size()) {
            // gems[start]가 여러개인 경우 start를 당긴다
            while (gem_map[gems[start]] > 1) {
                gem_map[gems[start]]--;
                start++;
            }
            // 당기기가 끝난 후, 현재 구간 길이가 min_len보다 짧으면 정답 갱신
            if (end - start + 1 < min_len) {
                min_len = end - start + 1;
                answer[0] = start + 1; // 인덱스 조정
                answer[1] = end + 1;   // 인덱스 조정
            }
        }
    }
    return answer;
}

---

🐛 시행착오 및 디버깅

• 문제점: 처음엔 start를 초기화하고 다시 탐색하는 방식을 떠올렸으나, 이는 비효율적임을 깨달았다.
• 해결: 애벌레가 기어가듯 start와 end가 모두 오른쪽으로만 이동하는 투 포인터 방식을 적용했다.
• 주의할 점:
  1. 인덱스 보정: 문제에서는 1번 진열대부터 시작하므로 결과 반환 시 +1을 해줘야 한다.
  2. 갱신 조건: 길이가 같은 구간이 여러 개일 경우 "시작 번호가 작은 것"을 반환해야 하므로, end - start + 1 < min_len (작을 때만 갱신) 조건을 사용해야 한다. s <= min_len을 쓰면 뒤쪽 구간으로 덮어씌워진다.

---

✅ 오늘의 회고

항목	내용
유형	Two Pointers (투 포인터), Sliding Window
체감 난이도	상 (구간 축소 로직이 핵심)
복잡도	시간: $O(N)$, 공간: $O(K)$ (K: 보석 종류)
새로 배운 것	while문을 이용한 윈도우 축소 테크닉, unordered_set 생성자로 벡터 넣기