보석 쇼핑 [LV. 3] (C++)

프로그래머스

다양한 종류의 보석들이 가게에 진열되어 있습니다. 당신은 모든 종류의 보석을 최소 한 개 이상 포함하는 가장 짧은 구간을 찾아야 합니다. 각 보석의 종류는 문자열로 주어지며, 이 문자열들의 배열이 주어질 때, 모든 보석을 포함하는 가장 짧은 구간을 구하는 문제입니다.

 

풀이 방법

이 문제는 슬라이딩 윈도우와 투 포인터 기법을 사용하여 해결할 수 있습니다. 기본 아이디어는 다음과 같습니다.

1. 보석 종류 파악: 주어진 배열 gems에 있는 보석의 종류를 파악합니다.
2. 슬라이딩 윈도우 초기화: 두 개의 포인터를 사용하여 현재 구간을 나타냅니다. 시작 포인터 start와 끝 포인터 end를 초기화합니다.
3. 구간 확장: end 포인터를 이동시키며 모든 보석 종류를 포함할 때까지 구간을 확장합니다.
4. 구간 축소 및 최적화: 모든 보석 종류를 포함하는 구간이 발견되면 start 포인터를 이동시키며 구간을 축소하고, 가장 짧은 구간을 찾습니다.
5. 결과 반환: 가장 짧은 구간의 시작과 끝을 반환합니다.

 

정답 코드

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

using namespace std;

vector<int> solution(vector<string> gems) {
    // 보석의 종류를 저장할 unordered_set
    unordered_set<string> gemKinds(gems.begin(), gems.end());
    // 각 보석의 개수를 저장할 unordered_map
    unordered_map<string, int> gemCount;
    
    // 모든 종류의 보석 개수
    int requireGemCnt = gemKinds.size();
    int foundGemCnt = 0; // 현재 구간에서 찾은 보석의 종류 개수
    int start = 0, end = 0; // 슬라이딩 윈도우의 시작과 끝
    int min_start = 0, min_end = gems.size(); // 최소 구간의 시작과 끝
    
    // 슬라이딩 윈도우 확장 및 축소
    while (end < gems.size()) {
        if (gemCount[gems[end]] == 0) {
            foundGemCnt++;
        }
        
        gemCount[gems[end]]++;
        end++;
        
        // 모든 종류의 보석을 포함한 경우
        while (foundGemCnt == requireGemCnt) {
            // 현재 구간이 최소 구간보다 짧은지 확인
            if (min_end - min_start > end - start) {
                min_end = end;
                min_start = start;
            }
            
            // start 포인터를 이동시켜 구간 축소
            gemCount[gems[start]]--;
            if (gemCount[gems[start]] == 0) {
                foundGemCnt--;
            }
            start++;
        }
    }
    
    // 결과 구간을 1-based index로 반환
    return {min_start + 1, min_end};
}