[C/C++] Lv4 프로그래머스 - 보석 쇼핑

programmers.co.kr/learn/courses/30/lessons/67258

코딩테스트 연습 - 보석 쇼핑

- 접근법

최대 10만개 데이터에서 모든 데이터 종류가 1개이상씩 보유하고 있는 가장 짧은 구간을 찾는 문제이다.

따라서, 이 문제는 빠른 시간안에 구간에서 보유하고있는 보석의 종류가 몇개인지 파악하는 방법만 알면 쉽게 풀린다.

 

0번 인덱스부터 차근 차근 map[보석종류] 에 개수들을 저장하면서 탐색을 한다.

어느 지점에서 map의 size가 곧 0번~어느 지점 까지의 보유하고있는 보석의 종류 개수이다.

 

그렇다면 0번에서 i번째 구간의 종류 개수가 아니라 j번째에서 i번째 (j~i)의 보석 종류 개수를 구하는 방법은 무엇일까?

 

여기서 투포인터 개념을 사용하게 되면 

left, right 포인터가 있고 right 포인터를 처음에 설명한 0번에서 right까지의 보석 종류를 파악하는 용도로 사용하고

left 포인터를 0번에서 left까지의 보석 종류를 감소시키면 된다. (종류의 개수가 다시 0이되면 map에서 삭제)

그렇게 되면, (left,right) 구간의 보석 종류 개수를 map.size() 함수 한번으로 파악할 수 있다.

 

따라서, 처음에 모든 보석 종류를 보유하는 첫 구간을 찾을 때까지 right 포인터를 계속 증가시키고

그 구간을 찾았다면 left 포인터를 증가시키면서 역으로 종류 개수들을 감소시켜준다.left 포인터를 증가시키고 다시 최대 보석 종류 개수가 아니라면 right 포인터를 증가시키면서 탐색을 하다보면O(N)에 최소 구간 (left, right)을 얻을 수 있다.

 

---

- 소스코드

#include <string>
#include <iostream>
#include <vector>
#include <unordered_map>
#define INF 9999999
using namespace std;
unordered_map<string,int> have_gems;
vector<int> solution(vector<string> gems) {
    vector<int> answer;
    int all_gems;
    int N=gems.size();
    int left=0,right=0;
    int answer_gap=INF,answer_left,answer_right;
    for(int i=0;i<N;i++) {
        if(have_gems[gems[i]]==0) {
            have_gems[gems[i]]++;
        }
    }
    all_gems=have_gems.size(); // 최대 보석 종류
    have_gems.clear();
    have_gems[gems[0]]++;
    
    while(left<=N-1 && right<=N-1) {
        if(have_gems.size()==all_gems) {
            if(answer_gap>right-left) {
                answer_gap=right-left;
                answer_left=left+1;
                answer_right=right+1;
            }
            have_gems[gems[left]]--;
            if(have_gems[gems[left]]==0) {
                have_gems.erase(gems[left]);
            }
            left++;
        }
        else {
            right++;
            if(right>N-1) continue;
            have_gems[gems[right]]++;
        }
    }
    answer.push_back(answer_left);
    answer.push_back(answer_right);
    return answer;
}