[우선순위큐] 백준 2841번 외계인의 기타연주 - JAVA

 

 

 

 

문제가 넘나 헷갈렸던 문제...

이 문제에 얼마나 시간을 쓴건지... ㅠㅠ

 

---

1. 출처

---

 

 

 

2841번: 외계인의 기타 연주

 

 

 

 

 

 

---

2. 설계

---

 

 

간단하다. 일단 나는 우선순위큐를 써서 프랫을 높은 순으로 정렬해줬다.

 

정렬의 경우 Comparable을 이용했다.

public static class Node implements Comparable<Node>{
		int line;
		int flat;
		
		public Node(int line, int flat){
			this.line = line;
			this.flat = flat;
		}
		
		@Override
		public int compareTo(Node o){
			return this.flat<o.flat?1:-1;
		}
	}

 

 

나는 각 줄별로 우선순위큐를 관리했다.

PriorityQueue<Node>[] touchList = new PriorityQueue[N];
		
for(int i=0;i<N;i++){
	touchList[i] = new PriorityQueue<>();
}

 

 

큐에 값이 없는 처음 시도의 경우는 그냥 넣어준다.

if(touchList[curLine].isEmpty()){//해당 라인의 터치가 없다면
	touchList[curLine].add(new Node(curLine, curFlat));
	result++;
}

 

 

이미 누르고 있는 프랫이 있는 경우는 아래와 같이 로직이 진행된다.

 

각 줄별로 현재 입력한 프랫보다 높은 것이 있으면 날려주고, result++를 해준다.

Node peek = touchList[curLine].peek();
				
//라인에 현재 터치보다 큰 플랫이 있다면
while (peek!=null && peek.flat>curFlat) {
	//손떼기
	touchList[curLine].poll();
	result++;
	peek = touchList[curLine].peek();
}

 

 

높은 것을 다 날려주면 내가 현재 입력한 프랫보다 1)같거나 2)낮거나 3)아예 없거나 3가지 중 하나이다.

 

같을 경우는 이미 눌려져 있기 때문에 continue하면 되고,

낮거나 아예 없는 경우는 어차피 현재는 내가 입력한 프랫보다 낮은 프랫만 있기 때문에 그냥 넣어주면 된다.

//손 댈 수 있는 상황 만들고,

//내가 누르려고 하는 터치와 플랫이 같다면 그냥 넘기기
if(peek!=null && peek.flat==curFlat) continue;

//작거나 아예 없다면 그냥 넣어도 됨
//손대기
touchList[curLine].add(new Node(curLine, curFlat));
result++;

 

 

 

//(1 ≤ N ≤ 500,000, 2 ≤ P ≤ 300,000)

 

 

줄(N)과 프랫(P)의 범위는 위와 같은데,

N = 500,000일 때, 300,000-1번 동안 한 줄에 2~300,000 프랫을 채우고 1 프랫을 넣는다고 쳐도 300,000회의 움직임이 필요하다.  즉, (300,000-1) + 300,000 회의 연산을 하고도 남은 200,000번이 똑같은 연산을 해도 1억번의 연산이 안넘는다고 판단했다. 즉, 1초가 넘지 않을 것이라 판단했고, 내가 짠 로직이 시간 초과는 나지 않겠구나 판단했다.

 

 

---

3. 전체 코드

---

 

import java.util.Scanner;
import java.util.PriorityQueue;

//(1 ≤ N ≤ 500,000, 2 ≤ P ≤ 300,000)
class 외계인의_기타_연주2
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();//5
		int P = sc.nextInt();//15
		
		PriorityQueue<Node>[] touchList = new PriorityQueue[N];
		
		for(int i=0;i<N;i++){
			touchList[i] = new PriorityQueue<>();
		}
		
		//test case
		int result = 0; 

		for(int T=0;T<N;T++){
			int curLine = sc.nextInt();
			int curFlat = sc.nextInt();
			
			if(touchList[curLine].isEmpty()){//해당 라인의 터치가 없다면
				touchList[curLine].add(new Node(curLine, curFlat));
				result++;
			}else{//터치가 있다면

				Node peek = touchList[curLine].peek();

				
				//라인에 현재 터치보다 큰 플랫이 있다면
				while (peek!=null && peek.flat>curFlat) {
					//손떼기
					touchList[curLine].poll();
					result++;
					peek = touchList[curLine].peek();
				}

				//손 댈 수 있는 상황 만들고,

				//내가 누르려고 하는 터치와 플랫이 같다면 그냥 넘기기
				if(peek!=null && peek.flat==curFlat) continue;

				//작거나 아예 없다면 그냥 넣어도 됨
				//손대기
				touchList[curLine].add(new Node(curLine, curFlat));
				result++;

			}			
			
		}//for end

		System.out.println(result);
		
	}
	
	public static class Node implements Comparable<Node>{
		int line;
		int flat;
		
		public Node(int line, int flat){
			this.line = line;
			this.flat = flat;
		}
		
		@Override
		public int compareTo(Node o){
			return this.flat<o.flat?1:-1;
		}
	}
	

}