[Programmers] 보석 쇼핑

안녕하세요. 이번 포스팅에서는 프로그래머스 보석 쇼핑이라는 문제를 풀어보도록 하겠습니다.

 

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

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

 

해당 문제는 투 포인터 알고리즘으로 해결하시면 됩니다.

 

우선 Set과 Map을 하나씩 각각 만들어 주고, 처음에 Set에 보석의 종류를 다 담아놓습니다.

["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"]

라면 

DIA, RUBY, EMERALD, SAPPHIRE가 Set에 담기게 됩니다.

 

그다음 처음 지점에 두 개의 포인터를 놓고

 

모든 Set의 원소가 적어도 한 번씩 등장할 때까지 두 번째 포인터를 이동시킵니다.

1. s = 0, e = 0 이라면,

 

["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"]

s = 0이고 e가 "SAPPHIRE"를 가리킬 때까지 이동됩니다.

 

2. 그다음 loop가 종료될 때 시작점의 카운트를 빼줍니다. 그래도 Set의 모든 원소의 정보를 담을 수 있다면 구간을 갱신해주시면 됩니다.

 

3. 시작점을 뺐는데, 다음 루프에서 모든 원소를 담지 못한다면 다시 1번으로 돌아가서 다시 e를 모든 원소가 담길 때까지  이동합니다. 위의 예에서는 DIA가 빠지게 되어도 <1, 6>에 모든 보석을 한번 이상 포함하므로 구간만 갱신됩니다.

 

4. 위의 과정을 더 이상 진행할 수 없을 때까지 반복합니다.

 

<소스 코드>

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

vector<int> solution(vector<string> gems) {
    vector<int> answer;
    answer.push_back(0); answer.push_back(1e9);

    set<string> _set;
    map<string, int> mp;

    for(int i = 0; i < gems.size(); i++)_set.insert(gems[i]); 
    int s = 0, e = 0;
    while(e < gems.size()) {
        while(_set.size()!=mp.size() && e < gems.size()) {
            mp[gems[e]]++; e++;
        }
        if(answer[1]-answer[0] > e-s) {
            answer[1] = e, answer[0] = s;
        }
        mp[gems[s]]--; 
        if(mp[gems[s]] == 0) mp.erase(gems[s]);
        s++;        
    }

    while(s < gems.size() && _set.size() == mp.size()) {
        if(_set.size() == mp.size()) {answer[1] = e, answer[0] = s;}
        mp[gems[s]]--; 
        if(mp[gems[s]] == 0) mp.erase(gems[s]);
        s++;
    }

    answer[0]++;
    return answer;
}

 

*저의 글에 대한 피드백이나 지적은 언제나 환영합니다.