[백준] Cow Lineup

https://www.acmicpc.net/problem/5926

5926번: Cow Lineup

투포인터 알고리즘을 이용하는 문제입니다.

 

우선 문제부터 간단하게 요약하면, 

소의 좌표와, 품종아이디가 들어옵니다. 좌표는 x좌표로 사진을 찍어 품종 아이디 모두를 담으려 하는데 필요한 x 최소 범위를 출력해야 합니다. 

 

<Solution>

투포인터 알고리즘을 이용합니다.

 

기본 로직은 아래와 같습니다.

1. 소를 x 좌표를 기준으로 sorting 2. 현재 left pointer 와 right pointer 사이에 모든 종류의 소가 없다면, right pointer를 늘려줌 2-1. 이 경우 x좌표의 차이를 구해서 매번 갱신시켜줌 3. 만약 양 포인터 사이에 모든 종류의 소가 들어 있다면, left pointer를 늘려줌

 

실제 구현은 아래와 같습니다.

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

using namespace std;

#define MAXN ((int)5e4)

int N;
struct COW{
    int x, id;
}cow[MAXN + 10];

set <int> ids;
// map <int, int> my_map;


void InputData(){
    cin >> N;
    for (int i=0; i<N; i++){
        cin >> cow[i].x >> cow[i].id;
        ids.insert(cow[i].id);
    }
}
bool compare(struct COW c1, struct COW c2){
    return c1.x < c2.x;
}
int solution(){
    map <int, int> my_map;
    int return_val = 1<<30;
    int total_ids = ids.size();
    int left_ptr = 0, right_ptr = 0;

    //sort by x cordinate
    sort(cow,cow+N, compare);
    int left_flag = 0;
    while(right_ptr < N){
        // cout << "left ptr : " << left_ptr << endl;
        // cout << "right ptr : "<<right_ptr << endl;
        if(!left_flag)my_map[cow[right_ptr].id]++;
        left_flag = 0;

        if(my_map.size() == ids.size()){
            return_val = min(return_val, cow[right_ptr].x - cow[left_ptr].x);
            if(return_val == 0) return return_val;
            my_map[cow[left_ptr].id]--;
            if(my_map[cow[left_ptr].id] == 0) {
                my_map.erase(cow[left_ptr].id);
            }
            left_ptr++;
            left_flag=  1;
            continue;
        }
        right_ptr++;

    }
    
    return return_val;



}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	
	int ans = -1;

	InputData();

    ans = solution();
	
	cout << ans << "\n";

	return 0;
}