[코드트리 챌린지] 특정 구간에 최소 하나는 있는 숫자

실력진단

 

[문제]

https://www.codetree.ai/training-field/search/problems/at-least-one-number-in-a-specific-section?&utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

[문제 풀이]

투 포인터를 이용한 문제이다.

문제에서 좌표를 숫자로 주어줬지만 좌표를 숫자가 아니라 index로 생각해보면 투 포인터를 이용해서 쉽게 풀린다는 것을 생각할 수가 있다.

우선 들어오는 값들을 vector<pair<int, int> > vec를 이용해 입력을 받은 뒤, 해당 벡터를 sort()함수를 이용해서 오름차순으로 정렬을 해주자.

그 후, 우선 set을 이용해 vec의 좌표값이 아닌 숫자들을 모두 데려오자. set은 중복값을 허용하지 않기 때문에 이처럼 만들면 해당 vec의 숫자들의 종류가 판별이 가능하다.

그리고 투 포인터를 이용해서 2번째 set인 num을 만든 뒤 a. num의 값이 set과 같을때 b. num의 값이 set보다 클때 c. num의 값이 set보다 작을때의 3가지 경우를 이용해서 start와 end의 위치를 조절하도록 하자.

또한, start위치에 있는 값을 set에서 바로 제거를 한다면 2,2,3,1,2,3,3,3,1,2,5와 같은 배열이 존재할때 앞에 있는 set에선 중복이 없으므로 중간에 있는 2를 파악을 못해준다. 이를 파악하기 위하여 map을 이용해서 파악을 해주자.

자세한 부분은 코드를 보면서 참고하도록 하자.

[회고]

처음엔 set에서 지워질때 중간값도 지워진다는 것을 생각 못했고 두번째로는 투 포인터에서 end의 범위를 <= n 이 아니라 < n으로 두어서 틀렸다. 세부사항에 주의하도록 하자.

[코드]

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

using namespace std;

int main() {
    //1. 1,000,000을 모두 처음에 지정하고 할 수는 없다.
    //그러니 벡터에 해당 숫자들을 모두 집어넣고 정렬을 하자.
    int n;
    cin>>n;
    vector<pair<int,int> > vec;
    set<int> st;
    set<int> num;
    map<int, int> mp;
    for(int i = 0;i<n;i++){
        //위치, 숫자 번호.
        pair<int,int> loc;
        cin>>loc.first>>loc.second;
        st.insert(loc.second);
        vec.push_back(loc);
    }
    sort(vec.begin(),vec.end());

    if(n == 1){
        cout<<0<<endl;
        return 0;
    }

    int start = 0;
    int end = 1;
    int total = 2100000000;

    //넣을때마다 find로 찾을순 없으니 map과 set을 이용하자.
    num.insert(vec[start].second);
    mp[vec[start].second] += 1;

    while(end <= n && start <= end){
        //만일 모두 다 들어왔다면
        if(num.size() == st.size()){
            total = min(total, vec[end - 1].first - vec[start].first);
        }
        //만약에 종류가 꽉 채워졌다면
        if(num.size() >= st.size()){
            //처음 위치를 조정하자.
            mp[vec[start].second] -= 1;
            if(mp[vec[start].second] == 0){
                num.erase(vec[start].second);            
            }
            start++;
        }
        else if(num.size() < st.size()){
            //아니라면 뒤에 end값을 계속 늘리자.
            num.insert(vec[end].second);
            mp[vec[end].second] += 1;
            end++;
        }
    }
    cout<<total<<endl;
    return 0;
}