programmers 보석 쇼핑

programmers 보석 쇼핑 : programmers.co.kr/learn/courses/30/lessons/67258#

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

 

2020 카카오 인턴십에 나온 보석 쇼핑 문제입니다.

 

처음에는 아무생각없이 이분탐색으로 체킹할 범위를 주고 범위를 줄여나가는 식으로 코딩하였는데,

생각해보니 이 '범위'를 파악하는게 결국 순차탐색이여서 O(N^2)가 된다는걸 보고 방법을 바꿨습니다.

 

풀이과정

1. set 을 이용해서 보석의 종류를 파악합니다.

2. 2개의 인덱스변수(lp, rp)를 가지고 map을 사용해서 1번만 순차탐색을 합니다.

3. lp, rp를 통해서 *현재 범위의 보석 종류를 파악할 수 있습니다.

아래 코드에 보시면 gemCnt라는 변수가 있는데, 이게 lp~rp 사이의 보석의 종류입니다.

map[gems[index]] 가 만약 0이라면, gems[index]를 map에 넣어줄 때 gemCnt의 값을 증가시킵니다.

0이 아니라면, 이미 있는 보석이니 그냥 ++를 통하여 현재 범위내의 gems[index]보석의 '갯수'만 증가시킵니다.

4. 이 gemCnt의 값이 1번에서 파악한 보석의 종류와 같다면,

  4.1 lp, rp의 범위를 통하여 최솟값을 파악하고, 정답을 갱신합니다.

  4.2 lp인덱스의 보석을 map에서 제거합니다.

     map[gems[lp]]-- 를 했을 때 0이 된다면 보석의 종류인 gemCnt가 1 감소됩니다.

  4.3 lp는 +1 하여 값을 증가시켜 범위를 갱신합니다.

5. gemCnt의 값이 보석의 종류보다 작다면

  5.1 rp를 증가시킵니다.

  5.2 rp의 범위가 보석갯수를 넘어가면 더 파악할 수 없기 때문에 break 됩니다.

  5.3 rp 보석을 map에 추가시킬 때 gemCnt도 4번과 마찬가지로 계산해줍니다.

6. 반복합니다.

 

설명을 적고보니 '투포인터' 문제인 것 같습니다.

투포인터 문제는 풀어본 경험이 별로없어서 이 문제를 기점으로 필요성을 느낀 것 같습니다.

조만간 '투포인터'에 대한 문제를 백준을 통해서 풀어봐야할 것 같습니다.

#include <string>
#include <vector>
#include <set>
#include <map>
using namespace std;

set<string> gem;
map<string,int> getgem;

vector<int> solution(vector<string> gems) {
    vector<int> answer;
    for(auto i : gems) gem.insert(i);
    
    int gs = gem.size();
    
    int ans_lp, ans_rp, ans_min=987654321;
    int lp = 0, rp = 0;
    int gemCnt = 1;
    getgem[gems[0]]++;
    while(1){
        if(gemCnt == gs){
            if(rp-lp<ans_min){
                ans_min = rp-lp;
                ans_lp = lp;
                ans_rp = rp;
            }
            string lp_str = gems[lp];
            getgem[lp_str]--;
            if(getgem[lp_str] == 0) gemCnt--;
            lp++;
        }
        else{
            rp++;
            if(rp>=gems.size()) break;
            
            string rp_str = gems[rp];
            if(getgem[rp_str] == 0) gemCnt++;
            getgem[rp_str]++;
        }
    }
    
    answer.push_back(ans_lp+1);
    answer.push_back(ans_rp+1);
    
    return answer;
}