1781 컵라면

일단,

먼저 다음과 같이 생각해보았다 (시간초과 남)

 

일단, 입력값을 컵라면 수 내림차순으로 정렬하는 것이다. 

예제의 경우

 

7
1 6
1 7
3 2
3 1
2 4
2 5
6 1

 

1 7

1 6

2 5

2 4

3 2

6 1

3 1 

 

=> 그리고 visit 배열을 만들어서

1) 만약에 그 시간에 방문한 적이 없다면, 방문표시하고

2) 혹시나 방문한 적이 있다면 그보다 작은 시간에 방문한 적 없다면 방문표시하는 것이다.

 

예를 들어서 

 

[1]

1 7 에서 기한은 1이므로

visit[1] = true 이다.

그리고 count = 7이 된다. (컵라면 수 )

 

[2]

그 다음 컵라면 수가 많은 1 6은 기한이 1이다.

하지만 이미 visit[1] = true 이므로

그냥 넘어간다.

 

[3] 

그 다음은 2 5 인데

visit[2] = false 이므로

visit[2] = true 를 만들고

count = 7+5 = 12 가 된다.

 

[4] 

2 4 의 경우

visit[2] = true 인데 visit[1] = true 이므로 

얘도 넘어간다.

 

이런식으로 하면 

1 7

2 5

3 2

6 1 (혹은 3 1) 

관련 숙제를 할 수 있어서

총 컵라면은 7 + 5 + 2 + 1 = 15 개 가 된다.

 

 

그런데 이 경우 시간초과가 나왔다. 

 

<시간 초과 난 코드>

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;


class Homework{
	
	
	int time;
	int noddles;
	
	
	Homework(int time, int noddles) {
		
		
		this.time = time;
		this.noddles = noddles;
	}
	
}


public class Main {	
	
	
	public static void main(String[] args) throws IOException {		
	
		  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	      StringTokenizer st = new StringTokenizer(br.readLine(), " ");
	    
	      int N = Integer.parseInt(st.nextToken());
	      
	  
	      PriorityQueue<Homework> pq = new PriorityQueue<>((a, b) -> {
	            if (a.noddles > b.noddles) {
	                return -1;
	            }else {
	            	return 1;
	            }
	        });
	
	      int time_max = Integer.MIN_VALUE;
	      
	      for(int i=0; i<N; i++) {
	    	  st = new StringTokenizer(br.readLine(), " ");
	    	  int a = Integer.parseInt(st.nextToken());
	    	  int b= Integer.parseInt(st.nextToken());
	    	  pq.add(new Homework(a,b));
	    	  
	    	  time_max = Math.max(time_max, a);
	      }
	      
	      
	      boolean visit[] = new boolean[time_max+1];   
	
	      int count = 0;
	      
	      while(!pq.isEmpty()) {	    	  
	    	  
	    	  Homework h = pq.poll();
	    
	    	  int time = h.time;
	    	  int noddles = h.noddles;	    	  
	    	  
	    	  if(!visit[time]) {   		
	    		 
	    		  visit[time] = true;
	    		  count+=noddles;    		  
	    		
	    	  }else {
	    		
	    		  // 이 부분에서 시간초과 나지 않았을까
	    		  solve:
	    		  for(int i=time-1; i>=1; i--) {
	    			  if(!visit[i]) {
	    				
	    				  visit[i] = true;
	    				  count+=noddles;
	    				 
	    				  break solve;
	    			  }
	    		  } 		  
	    		  
	    	  }     	  
	      }
	      
	      
	      
	      System.out.println(count);
	      
	      
	}
}

 

 

 

 

 

 

 

 

그래서 블로그를 참고하여 다른 방법을 찾아보았다.

이때 아이디어는 다음과 같다.

 

<1> 입력값을 데드라인 날짜가 큰 순서대로 정렬한다.

list 를 이용해서 정렬하는데,

7
1 6
1 7
3 2
3 1
2 4
2 5
6 1

 

6 1

3 2

3 1

2 4

2 5

1 6 

1 7

 

와 같이 된다. 

 

그 후 for문을 이용해서,

 

<2 > 데드라인이 큰 경우부터 우선순위 큐에 넣는데,

컵라면 수가 많을수록 앞쪽에 위치하도록 정렬한다.

 

그리고 각 for문 마다 컵라면의 수가 가장 많은 값들을 더해주면 된다.

(for문에서 index를 200,000 부터 하는 이유는, 문제에서 각 문제의 데드라인이 N 이하의 자연수라고 하였고, 

N의 범위는 1부터 200,000 까지 라고 하였으므로) 

 

자세히 설명하면,

 

1)

맨 처음에 데드라인이 가장 큰 경우는 6이므로 우선순위 큐에 넣어준다.

정답으로 출력할 변수를 result 라고 했을 때, 

우선순위에 들어있는 것 중 가장 컵라면의 수가 많은 값을 뺴서 result에 더해준다. 

 

우선순위 큐 : (6 1)

-> result = 1

 

 

 

2) 두 번째로 데드라인이 큰 경우는 3이다.

 

우선순위 큐 : (3 2), (3 1)

-> result = 1+2 = 3

 

=> 우선순위 큐에는 (3 1) 만 남게 된다. 

 

 

3) 세번째로 데드라인이 큰 경우는 2이다.

 

우선순위 큐 : (2 5), (2 4), (3 1)

-> result = 1 +2 + 5 = 8

 

=> 우선순위 큐에는 (2 4) (3 1) 이 남게 된다. 

 

 

4) 네 번쨰로 데드라인이 큰 경우는 1이다.

 

우선순위 큐 : (1 7), (1 6), (2 4), (3 1)

-> result = 1+2+5+7 = 15

 

=> 우선순위 큐에는 (1 6), (2 4), (3 1) 이 남게 되며 끝이 난다.

 

 

결과적으로 답은 15가 된다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

class Homework{
	
	int deadline;
	int noddles;
	
	Homework(int deadline, int noddles) {	
		
		this.deadline = deadline;
		this.noddles = noddles;
	}
}


public class Main {
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int N=Integer.parseInt(st.nextToken());
		ArrayList<Homework> list = new ArrayList<>();
		
		for(int i=0; i<N; i++) {
			
			st = new StringTokenizer(br.readLine(), " ");
			int a = Integer.parseInt(st.nextToken());
			int b= Integer.parseInt(st.nextToken());
			list.add(new Homework(a,b));	
			
		}
		
		
		// 데드라인 내림차순 정렬 
		list.sort(new Comparator<Homework>() {
			
			@Override
			public int compare(Homework h1, Homework h2) {
				return h2.deadline - h1.deadline;
			}
			
		});
		
		// 컵라면 수 내림차순 정렬
		PriorityQueue<Homework> pq = new PriorityQueue<>(new Comparator<Homework>() {
		
			@Override
			    public int compare(Homework h1, Homework h2) {
				
				 	return h2.noddles - h1.noddles; 
			    }
	    	});       
		
		
		int index = 0;
		int result = 0;
		
		for(int i=200000; i>=1; i--) {
			
			while(index< list.size() && list.get(index).deadline ==i) {
		
				pq.add(list.get(index));
				index++;
			}
			
			
			if(!pq.isEmpty()) {
				
				Homework h = pq.poll();			
				result+= h.noddles;
			}			
		}
		
		System.out.println(result);	
		
	}
}

 

 

참고 블로그 : https://velog.io/@anwlro0212/%EB%B0%B1%EC%A4%80-1781-%EC%BB%B5%EB%9D%BC%EB%A9%B4-JAVA

[백준] 1781 - 컵라면 (JAVA)