코딩테스트 : 보석 쇼핑

문제 설명
해당 문제는 진열대에 나열된 보석들 중 모든 종류의 보석을 하나 이상 포함하는 가장 짧은 구간을 찾는 문제이다.

예를 들어 보석 종류가 4개라면 이 4가지 종류를 모두 포함하는 가장 짧은 구간의 시작과 끝 인덱스를 반환해야 한다.

 

핵심 방법
슬라이딩 윈도우 + 해시맵(map) 을 사용하여 현재 구간 내 보석의 종류를 세고,
모든 종류가 포함되었을 때 왼쪽 포인터를 줄이며 최소 구간을 갱신하는 방식이다.

 

슬라이딩 윈도우(Sliding Window) 기법은 배열이나 리스트에서 일정한 구간(윈도우)을 유지하며 왼쪽, 오른쪽 포인터를 이동시키는 방식으로 문제를 푸는 알고리즘 기법이다. Two Pointer 기법과 비슷하며 두 포인터의 구간을 검색하고 진행 방향이 같다는 것이 핵심이다.

 

Two Pointer 기법에 대한 자세한 내용은 아래 블로그에서 확인할 수 있다.

Two Pointer 기법

 

#include <string>
#include <vector>
#include <map>
#include <set>
#include <climits>

using namespace std;

vector<int> solution(vector<string> gems) {
    map<string, int> m; // 현재 윈도우 내 보석 종류별 개수를 저장
    vector<vector<int>> results; // 가능한 구간들을 저장

    set<string> s;
    for(string str : gems)
        s.insert(str); // 보석 종류를 set으로 구분하여 전체 종류 수를 파악

    int gemsCount = s.size(); // 전체 보석 종류 수

    int start = 0; // 현재 슬라이딩 윈도우의 시작 인덱스
    string frontGem = gems[0]; // 현재 윈도우의 가장 앞에 있는 보석

    int current = 0; // 현재 슬라이딩 윈도우의 끝 인덱스
    bool firstFind = false; // 처음으로 모든 종류를 포함한 윈도우를 찾았는지 여부

    for(int i = 0; i < gems.size(); i++)
    {
        current = i;
        m[gems[i]]++; // 현재 보석을 윈도우에 포함

        if(m.size() == gemsCount && !firstFind) // 처음으로 모든 보석 종류를 포함한 경우
        {
            results.push_back({start + 1, current + 1}); // 1-based 인덱스로 저장
            firstFind = true; // 첫 발견 표시
        }

        bool init = false;

        while(m[frontGem] > 1) // 가장 앞 보석이 중복된 경우, 윈도우를 줄이기 시도
        {
            start++; // 시작 인덱스를 앞으로 이동
            m[frontGem]--; // 해당 보석 개수 감소
            frontGem = gems[start]; // 새로운 앞 보석 설정
            init = true;
        }

        if(firstFind && init) // 줄이기 이후에도 모든 종류 포함 중이면 저장
            results.push_back({start + 1, current + 1});
    }

    int temp = INT_MAX;
    vector<int> result;
    for(vector<int> v : results) // 저장된 구간 중 가장 짧은 구간 선택
    {
        if(temp > v[1] - v[0])
        {
            temp = v[1] - v[0];
            result = v;
        }
    }

    return result; // 가장 짧은 구간 반환
}