[JUNGOL] 1828 냉장고

 

그리디 문제다 정렬을 시키고 뒤에 화학물질부터 보면된다

냉장고의 (x,y)라고 할 때 y를 기준으로 잡고 다음 화학물질의 x가

현재 y를 넘는지 안넘는지로 판단할 수 있다

 

넘는다면 같은 냉장고안에 넣을 수 있다

그리고 y값은 더 뒤에있는 값으로 초기화해준다

 

그리고 범위를 안넘으면 냉장고를 늘려주면 된다!

 

자바는 pair가 없어서 구현해야한다..!

그리고 pq는 minheap이다!!

 

JAVA 소스코드

import java.util.PriorityQueue;
import java.util.Scanner;
 
class Pair implements Comparable<Pair> {
    int first, second;
    
    Pair(int f, int s) {
        this.first = f;
        this.second = s;
    }
    
    public int compareTo(Pair p) {
        if(this.first > p.first) {
            return -1; 
        }
        else if(this.first == p.first) {
            if(this.second > p.second) {
                return -1;
            }
        }
        return 1; 
    }
}
 
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n =sc.nextInt();
        PriorityQueue<Pair> pq = new PriorityQueue<Pair>();
        
        for(int i=0;i<n;i++) {
            int x=sc.nextInt();
            int y=sc.nextInt();
            x+=300; y+=300;
            Pair p = new Pair(y,x);
            pq.add(p);
        }
        int ans=1;
        int pos = pq.poll().second;
        while(!pq.isEmpty()) {
            int x = pq.peek().first;
            int y = pq.poll().second;
            if(x>=pos) pos = Math.max(pos, y);
            else {
                ans+=1; pos=y;
            }
        }
        System.out.println(ans);    
    }
}
 

 

C++로도 먼저 풀어봤다..!

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int n;
 
int main() {
    scanf(" %d", &n);
    priority_queue<pair<int, int>> pq;
 
    for (int i = 0; i < n; i++) {
        int x, y; scanf(" %d %d", &x, &y);
        x += 300; y += 300;
        pq.push({ y,x });
    }
    int ans = 1;
 
    int pos = pq.top().second; pq.pop();
    while (!pq.empty()) {
        int x = pq.top().first;
        int y = pq.top().second;
        pq.pop();
        if (x >= pos) pos = max(pos, y);
        else {
            ans += 1; pos = y;
        }
    }
    printf("%d\n", ans);
}