문제 출처

1. 문제설명

• 문자열로 된 보석 리스트가 주어진다.
• 모든 종류의 보석을 1개 이상 포함하는 가장 짧은 구간(인덱스 번호) 계산

2. 입/출력

• 입력
  • 진열대 번호 순서대로 보석들의 이름이 저장된 배열 gems
• 출력
  • 모든 보석을 하나 이상 포함하는 가장 짧은 구간의 시작 진열대 번호와 끝 진열대 번호를 차례대로 배열에 담아서 return

3. 문제 분류

• Two pointer
  • 조건을 만족하는 구간을 탐색하는 알고리즘
  • 알고리즘 수행에는 구간의 시작점, 끝점을 위한 변수가 필요하다.
  • 일반적인 종료 조건은 끝점이 탐색 지점의 끝보다 작을 때이다.
    • 구간을 탐색하는 거니까 어쩌면 당연한 말

4. 알고리즘 설계

• 알고리즘 수행에 앞서, 유일한 보석의 개수가 필요하다.
  • set<string> unique(gems.begin(), gems.end())
  • set은 중복을 허용하지 않는 자료구조이다.
  • 만약 중복된 원소가 insert되면 무시된다고 생각하면 이해가 빠르다.
• 투 포인터 수행을 위한 start, end 초기화
  • start는 원소의 가장 처음인 0으로 지정
  • unordered_map을 통해 보석의 개수를 카운팅
  • 유일한 보석의 개수와 unordered_map의 size가 같아지는 인덱스를 찾는다.
    • 이 인덱스가 end가 된다.

• 여기까지 수행했다면 가장 앞 부분의 모든 보석을 포함하는 가장 짧은 구간을 찾은 것이다.

• 이 구간은 언제나 가장 짧은 구간이 될 수 있을까?
  • 정답은 아니다.
• 보석을 편의상 번호로 명명하고 다음 리스트를 살펴보자
  • {1, 2, 2, 1, 1, 3, 4, 1}
  • 0번째인 1부터 유일한 4에 해당하는 인덱스(6)로 초기화 될 것이다.
    • 이 때의 리스트는 {1, 2, 2, 1, 1, 3, 4}가 된다.
    • 1은 3개, 2는 2개 3과 4는 1개씩이다.
  • 중복되는 원소가 있으니, 개수를 줄인다면 구간이 줄어들 것이다.
  • start의 위치인 0번째부터 지워보자
    • 지워도 여전히 1은 2개 있어서 여유롭다.
  • 1번째 위치의 2를 지워도 2가 한개가 남아있다.
  • 2번째 위치의 2를 지우면 2가 0개가 된다.
  • 주어진 리스트에서는 가장 짧은 구간을 구하는 데 성공했다.
• 여기까지 계산했을 때, 더 짧은 리스트는 절대로 존재할 수 없는가?
  • 뒤에 있는 원소를 붙였는데 1개 이상의 보석을 가지는 더 짧은 리스트가 될 수 있다.
• 우리는 위에서 2를 지웠을 때 0개가 된다는 점을 이용해 구간을 구했다.
  • 그렇다면 뒷쪽에서 가장 먼저 만나는 2를 찾고,
  • 이전 구간과 새로운 구간의 길이를 비교하면 된다.
• 2를 찾지 못한다면, 인덱스가 배열의 크기보다 커지기 때문에 바로 종료하면 된다.
• 2를 찾지 못하면 모든 보석을 포함한다는 조건을 무너뜨리기 때문이다.

5. 전체 코드

#include <bits/stdc++.h>
using namespace std;

vector<int> solution(vector<string> gems) {
    set<string> unique(gems.begin(), gems.end());
    unordered_map<string, int> MAP;
    vector<int> ans;

    int s = 0, e = gems.size() - 1;

    for (int i = 0; i < gems.size(); i++) {
        MAP[gems[i]]++;
        if (MAP.size() == unique.size()) {
            e = i;
            break;
        }
    }

    ans = { s + 1, e + 1 };
    int cmp = e - s;

    while (e < gems.size()) {
        string cur = gems[s++];
        MAP[cur]--;

        if (MAP[cur] == 0) {
            e++;
            while (e < gems.size()) {
                MAP[gems[e]]++;
                if (gems[e] == cur) break;
                e++;
            }
        }

        if (e - s < cmp) {
            ans = { s + 1, e + 1 };
            cmp = e - s;
        }
    }

    return ans;
}