프로그래머스 - 보석 쇼핑 - C++

hansol_Shin·2021년 5월 17일

알고리즘 프로그래머스

Algorithm

목록 보기

9/12

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

문제설명

연속된 구간안에서 모든 보석종류가 포함된 최소 길이의 구간을 return하는 문제이다.
파라메터로 vector<string> gems가 주어지고 gems에는 보석이 순차적으로 나열되어있다.
최소 길이 구간이 같은 경우 시작 index가 최소인 구간을 return한다.
gems의 최대 길이가 100,000으로 주어진다.

접근 방법

gems의 최대 길이가 100,000이므로 2중 for문을 사용할 수 없다. 따라서 2-pointer 알고리즘을 사용해야 한다.
2-pointer 알고리즘은 O(N), 선형시간에 연속된 구간에 대한 문제를 해결하는 알고리즘이므로 이 알고리즘을 모른다면 공부하고 이 문제를 풀어보는것을 추천한다.
파라메터로 vector<string> gems만 주어지고, 보석 종류의 총 개수는 주어지지 않으므로 unordered_set으로 종류의 개수를 구한다.
이후 unordered_map을 사용하여 구간 안에 존재하는 보석을 체크하며 2개의 포인터를 조절한다.
unordered_map의 size()함수를 사용하여 unordered_set으로 구한 보석 종류의 개수와 비교하여 같을 때 구간을 기록한다.
while문을 돌면서 마지막 pointer가 범위를 초과하면 종료한다.

코드

#include <string>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <iostream>
using namespace std;
unordered_map<string,int> m;
unordered_set<string> set;
vector<int> solution(vector<string> gems) {
    vector<int> answer;
    answer.push_back(0);
    answer.push_back(0);    
    int Min = 1000001;  // 가장 짧은 구간의 길이 저장변수
    int s=0,e=-1;   // two pointer 변수
    // 보석 종류의 수 구하기
    for(auto g :gems){
        set.insert(g);
    }
    int n = set.size();
    while(1){
        if(m.size()==n){    // 모든 종류가 다 찾아진 경우
            if(e-s<Min){    // 가장 짧은 구간 갱신
                Min = e-s;
                answer[0]=s+1;
                answer[1]=e+1;
            }
            m[gems[s]]--;
            if(m[gems[s]]==0){  // 특정 보석의 수가 0이면 삭제
                m.erase(gems[s]);
            }
            s++;            
        }
        else if(e==gems.size()-1){  // gems의 범위를 초과할 경우
            break;
        }
        else{   
            e++;
            m[gems[e]]++;
        }
    }
    return answer;
}