[2020 카카오 인턴십] 보석 쇼핑

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

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

---

[풀이과정]

구해야하는 것 : 보석을 모두 포함하는 가장 짧은 구간의 시작점과 종료점

 

 

1) 먼저 보석의 종류들을 set에 모두 담아둔다. (vector아닌 set에 담아두는 이유 : set은 중복 원소를 포함하지 않으므로, 보석이 종류들만 얻을 수 있다.

 

2) 투 포인터를 사용하여 가장 짧은 구간의 시작점을 찾아준다.

 

start와 end를 각각 0으로 초기화하고, 다음과 같은 두 가지의 경우로 나뉘어진다.

 

- 내가 현재까지 획득한 보석이 보석의 종류보다 적으면 end 를 증가

- 내가 현재까지 획득한 보석이 보석의 종류와 같다면 start를 증가 (같다면, set의 크기와 map의 크기가 같다.)

 

나는 이 획득한 보석을 map에 가장 최근 인덱스와 함께 저장해두었다.

 

	start	end
	0	0 (map에 아무값도 없으므로 map["DIA"] = 0, end++)
	0	1 (map에 DIA만 있고 RUBY는 없으므로 map["RUBY"] = 1, end++)
	0	2 (map에 DIA, RUBY 있는데, 또 RUBY 가 들어옴 : map["RUBY"] = 2로 업데이트하고, end++)
	0	3 (map에 DIA, RUBY 있는데, 또 DIA 가 들어옴 : mp["DIA"] = 3으로 업데이트하고, end++)
	0	4 (map에 DIA, RUBY 있는데, 또 DIA 가 들어옴 : mp["DIA"] = 5로 업데이트하고, end++)
	0	5 (map에 DIA, RUBY 있는데, EMERALD 가 들어옴 : mp["EMERAD"] = 6, end++)
	0	6 (map에 DIA, RUBY, EMERALD 있는데, SAPHIRE 가 들어옴 : mp["SAPHIRE"] = 7, end++)
모든 보석 다 채움 end - start = 7 - 1 = 6	0->1 (모든 종류의 보석을 남았으므로, start를 움직이기 시작, mp[gems[0(start)]] = mp["DIA"] = 5이므로, 그 값을 아직 지우진 말고, start ++)	7 (이제 모든 종류의 보석을 담아 map의 크기와 set의 크기가 같아졌다.)
모든 보석 다 채움 end - stat = 7 -2 =5	1->2 (gems[1] = RUBY, mp["RUBY"] = 2인데, 현재 start(1) 과 다르므로 건들지 않고, start ++)	7
모든 보석 다 채움 end - start = 7-3 =4	2->3 (mp["RUBY"] = 2 = start 이므로, RUBY를 map에서 제거한다. 그리고 start++)	7
	3	(방금 전에, map에서 RUBY를 뺏기 때문에 map에 DIA, EMERALD, SAPHIRE만 있다. mp["DIA"]는 이미 map에 존재한다.)
		이제 end가 v의 배열에 끝 부분까지 검사했기 때문에 더 할 수 있는게 없으므로 while 문을 종료한다.

 

투포인터가 진행되는 과정을 간단히 표와 글로 작성해보았다. 

 

3) 모든 보석을 채우는 경우에 벡터에 넣어둔다.

 

4) 커스텀한 sort 옵션으로 문제의 조건에 맞게 정렬해주면 답을 구할 수 있다.

---

소스코드

#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <set>

using namespace std;

bool compare(pair<int,int> p1,pair<int,int> p2){
    int minus1 = p1.second - p1.first;
    int minus2 = p2.second - p2.first;
    if(minus1==minus2){
        return p1.first < p2.first;
    }else{
        return minus1 < minus2;
    }
}

vector<int> solution(vector<string> gems) {
    vector<int> answer;
    
    map<string,int> mp;
    set<string> s;
    
    for(int i=0;i<gems.size();i++){
        s.insert(gems[i]);
    }
    
    
    int start = 0;
    int end = 0;
    vector<pair<int,int>> v;
    
    while(1){
        if(s.size()==mp.size()){
            v.push_back({start,end});
            
            if(mp[gems[start]]==start){
                mp.erase(gems[start]);
            }
            
            start++;
        }else if(end==gems.size()){
            break;
        }else{
            mp[gems[end]]=end;
            end++;
        }
    }

    sort(v.begin(),v.end(),compare);

    answer.push_back(v[0].first+1);
    answer.push_back(v[0].second);
    return answer;
}