BOJ_1781_컵라면

시작하면서

해당 문제는 pq 외에도 그리디한 방법으로 해결해 볼 수 있는데, 포스팅에서는 pq로 푸는 방법에 대해 고민해봤습니다.

여러 알고리즘 로직을 세워서 문제를 접근했는데, 9%에서 "틀렸습니다." 가 나와서 참으로 힘들게 했던 문제입니다.

문제 접근 시 데드라인과 컵라면 수를 잘 고려해봐야 하는데

데드라인은 우선순위를 높게, 같다면 컵라면 수는 더 큰것을 정해서 큐에 담아주어야 합니다.

 

처음 생각한 점

우선순위 큐를 지정했을 때 정렬 순서를 

1. 데드라인은 우선순위를 높게

2. 컵라면 수는 더 큰것을 지정

3. 우선순위 큐에 Max-heap 구성 (데드라인 기준으로 push 할 경우 더 높은 숫자의 데드라인이 pop되는 것을 고려)
ex) pq에 {1,7} 이 있다고 고려 하면, 새롭게 {2,6} 이 들어오게 됐을 때 {1,7} {2,6} 인 경우 {1,7}이 pop되는 것을 방지

코드는 다음 처럼 구성하였습니다.

위 처럼 구성하게 되면 데드라인에 대해서 max-heap 을 구성하게 됩니다. 

전체 코드를 구성하면 다음과 같습니다. 

틀린코드

 

이 방법 대신에 좋은 방법에 대해 서치해보았습니다. 

우선순위 큐에 push 할 때 정렬하는 것이 아니라, 

이미 데드라인으로 정렬된 상태에 list에서 값을 빼면서 

큐의 사이즈가 데드라인보다 작은 경우에만 push하고 

그렇지 않으면 pop 하는 구조의 코드입니다. 

이렇게 구성하게 되면 위에서 코드를 구성했을 때 입력 순서에 따라 정렬이 달라지는 것을 예방할 수 있습니다.

 

알고리즘 로직

알고리즘 로직을 단순화 해보면 다음과 같습니다.

1) 사전에 ArrayList에 데드라인으로 정렬된 쌍 값을 add 하게 됩니다.

2) 이후, pq에 push할 경우 pq 사이즈가 데드라인보다 작은 경우에만 pq에 값을 삽입합니다. 

3) pq에 남은 값을 모두 더해줍니다. 

 

코드

import java.util.*;
import java.io.*;
 
public class Main {
 
    static class pos{
        int x;
        int y;
        pos(int x,int y){
            this.x=x;
            this.y=y;
        }
    }
    
    public static void main(String[] args) throws Exception{
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        PriorityQueue<pos> q = new PriorityQueue<>(1, new Comparator<pos>() {
 
            @Override
            public int compare(pos o1, pos o2) {
                // TODO Auto-generated method stub
                return o1.y-o2.y;
            }
        });
        //PriorityQueue<Integer> q = new PriorityQueue<>();
        
        ArrayList<int[]> al = new ArrayList<>();
        
        for(int i=0; i<n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int deadline = Integer.parseInt(st.nextToken());
            int noodle = Integer.parseInt(st.nextToken());
            al.add(new int[] {deadline, noodle});
            //q.add(new int[] {deadline, noodle});
        }
        
        Collections.sort(al, new Comparator<int[]>(){
 
            @Override
            public int compare(int[] o1, int[] o2) {
                // TODO Auto-generated method stub
                if(o1[0]==o2[0]) {
                    return o2[1]-o1[1];
                }else
                    return o1[0]-o2[0];
            }
            
        });
        
        
        
        int temp = al.get(0)[0];
        int ans = 0;
        
        for(int i=0; i<al.size(); i++) {
            //q.add(new pos(al.get(i)[0],al.get(i)[1]));
            int a =al.get(i)[0];
            int b =al.get(i)[1];
            q.add(new pos(al.get(i)[0], al.get(i)[1])) ;
            if(a<q.size()) {
                q.poll();
            }
        }
        while(!q.isEmpty()) {
            ans+=q.poll().y;
        }
        //System.out.println(ans);
        
//        int ans = 0;
 
//        for(int[] i : q) {
//        System.out.println(i[0]+" "+i[1]);
//    }
        
        System.out.println(ans);
    }
}