문제 설명

개발자 출신으로 세계 최고의 갑부가 된 어피치는 스트레스를 받을 때면 이를 풀기 위해 오프라인 매장에 쇼핑을 하러 가곤 합니다. 어피치는 쇼핑을 할 때면 매장 진열대의 특정 범위의 물건들을 모두 싹쓸이 구매하는 습관이 있습니다. 어느 날 스트레스를 풀기 위해 보석 매장에 쇼핑을 하러 간 어피치는 이전처럼 진열대의 특정 범위의 보석을 모두 구매하되 특별히 아래 목적을 달성하고 싶었습니다. 진열된 모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 구간을 찾아서 구매

예를 들어 아래 진열대는 4종류의 보석(RUBY, DIA, EMERALD, SAPPHIRE) 8개가 진열된 예시입니다.

진열대 번호	1	2	3	4	5	6	7	8
보석 이름	DIA	RUBY	RUBY	DIA	DIA	EMERALD	SAPPHIRE	DIA

진열대의 3번부터 7번까지 5개의 보석을 구매하면 모든 종류의 보석을 적어도 하나 이상씩 포함하게 됩니다.

진열대의 3, 4, 6, 7번의 보석만 구매하는 것은 중간에 특정 구간(5번)이 빠지게 되므로 어피치의 쇼핑 습관에 맞지 않습니다.

진열대 번호 순서대로 보석들의 이름이 저장된 배열 gems가 매개변수로 주어집니다. 이때 모든 보석을 하나 이상 포함하는 가장 짧은 구간을 찾아서 return 하도록 solution 함수를 완성해주세요. 가장 짧은 구간의 시작 진열대 번호와 끝 진열대 번호를 차례대로 배열에 담아서 return 하도록 하며, 만약 가장 짧은 구간이 여러 개라면 시작 진열대 번호가 가장 작은 구간을 return 합니다.

제한사항

gems 배열의 크기는 1 이상 100,000 이하입니다.
- gems 배열의 각 원소는 진열대에 나열된 보석을 나타냅니다.
- gems 배열에는 1번 진열대부터 진열대 번호 순서대로 보석이름이 차례대로 저장되어 있습니다.
- gems 배열의 각 원소는 길이가 1 이상 10 이하인 알파벳 대문자로만 구성된 문자열입니다.

풀이

문제 자체는 간단해보이나, 효율성 테스트까지 만점을 받기 위해서는 자료구조와 탐색 알고리즘에 대한 지식이 필요한 문제였습니다.

문제를 다음과 같이 두 가지 단계로 나누어 접근해보겠습니다.

구간 나누기
해당 구간이 모든 보석을 포함하는지 확인하기

먼저 구간을 나누는 경우 가장 단순한 접근으로는 모든 구간을 확인하는 방법이 있습니다. 이러한 경우 시간복잡도는 O(N^2)이고 N의 최댓값이 100,000이므로 구간을 나누는 것만으로도 시간 초과가 발생하게 됩니다. 이때 투포인터를 이용하면 선형 자료구조를 O(N)만에 탐색할 수 있습니다. 확인할 구간의 양 끝점을 가리키는 포인터(변수) 2개를 선언하고 오른쪽 끝의 포인터를 점점 증가시키다가 모든 보석을 포함하게 될 경우, 이번엔 왼쪽 끝의 포인터를 모든 보석이 포함되는 한까지 점점 증가시키는 작업을 반복합니다. 이러한 과정을 통해 모든 보석을 포함하는 최소 구간을 찾을 수 있습니다.

그렇다면 특정 구간이 모든 보석을 포함하는지는 어떻게 알 수 있을까요? 모든 종류의 보석을 한 번씩만 담고있는 types 배열을 생각해봅시다. 탐색하려는 특정 구간의 길이가 N이고 모든 보석 종류의 갯수를 M이라고 할 때, types 배열에 존재하는 모든 종류를 일일이 구간과 비교하는데 걸리는 시간복잡도는 O(MlogN)이고, 위에서 언급한 구간을 나누는 작업까지 고려하면 O(N^2logN)으로 시간 초과를 면치 못하게 됩니다.

따라서 특정 구간에 존재하는 모든 보석 종류를 빠르게 확인할 방법이 필요합니다. 이는 set과 map 자료구조를 통해 구현할 수 있습니다. 투포인터를 통한 탐색 과정에서 오른쪽 끝의 포인터를 증가시킬 때는 추가된 보석을 카운팅하고, 왼쪽 끝의 포인터를 증가시킬 때는 제외된 보석을 빼줍니다. 이를 통해 특정 구간에 존재하는 모든 보석 종류의 집합을 얻을 수 있고, 이 집합의 크기와 위에서 언급한 types 배열의 길이가 같아질 때 모든 보석의 종류가 있음을 알 수 있습니다. 포인터가 옮겨갈 때마다 한 번씩 진행되는 삽입/삭제의 시간복잡도는 O(logN)이고, 구간을 나누는 경우와 결합하면 최종적으로 O(NlogN)의 시간복잡도를 가지며 N = 100,000일 때에도 시간 초과가 발생하지 않음을 알 수 있습니다.

전체 코드

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

vector<int> solution(vector<string> gems) {
    vector<int> answer(2);
    
    vector<string> types = gems;
    sort(types.begin(), types.end());
    types.erase(unique(types.begin(), types.end()), types.end());
    
    int l = 0, r = -1, len = 1e9;
    queue<string> q;
    set<string> s;
    map<string, int> count;
    
    while(++r < gems.size()) {
        q.push(gems[r]);
        s.insert(gems[r]);
        count[gems[r]]++;
        
        while(s.size() == types.size()) {
            if(r-l < len) { len = r-l; answer[0] = l+1; answer[1] = r+1; }
            if(--count[q.front()] == 0) s.erase(q.front());
            q.pop();
            l++;
        }
    }

    return answer;
}

Android Developer

[프로그래머스] 보석 쇼핑 풀이 (2020 카카오 인턴십)

문제 설명

제한사항

풀이

전체 코드