백준 28107: 회전초밥(java)

문제

---

풀이

 

손님 큐와 초밥 큐, 2개의 우선순위 큐를 이용해 풀이한다.

 

customer 우선순위 큐에 { 초밥 종류, 손님 번호 }를 원소로 가지는 배열을 삽입한 후 초밥 종류에 따라 오름차순으로 정렬하고, 같은 종류의 초밥일 경우 손님 번호 순으로 정렬한다.

PriorityQueue<int[]> customer=new PriorityQueue<>(new Comparator<int[]>() {
	@Override
	public int compare(int[] o1, int[] o2) {
		if(o1[0]==o2[0]) {	//같은 초밥일 경우
			return o1[1]-o2[1];	//손님 순서로 정렬
		}
				
		return o1[0]-o2[0];	//초밥 종류로 정렬
	}
});

 

이때 Comparator 수정을 통해 정렬 규칙을 추가해 주어야 한다.

 

이제 만들어진 초밥을 오름차순으로 저장할 sushi 우선순위 큐를 생성하고 큐에 요소들을 삽입한다.

customer 첫 번째 요소의 초밥 종류와 sushi 첫 번째 요소를 비교한다.

int[] res=new int[N];	//손님 별 먹은 횟수 저장할 배열

//customer 첫 번째 요소의 초밥 종류와 sushi 첫 번째 요소 비교
if(customer.peek()[0]==sushi.peek()) {	//같으면
	sushi.poll();	//sushi에서 제거
	res[customer.poll()[1]]++;	//customer에서 제거한 후 res++
}
else if(customer.peek()[0]>sushi.peek()) {	//customer의 초밥 종류가 더 크면
	sushi.poll();	//남은 customer 전체에서 해당 초밥을 먹을 손님이 없으므로 sushi에서 삭제
}
else {	//sushi가 더 크면
	customer.poll();	//다음 손님으로 이동하기 위해 customer에서 삭제
}

while문을 이용해 위의 반복을 customer 또는 sushi가 공백 상태가 될 때까지 반복하면 된다.

 

전체 코드

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

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());	//손님
		int M=Integer.parseInt(st.nextToken());	//초밥 종류
			
		PriorityQueue<int[]> customer=new PriorityQueue<>(new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				if(o1[0]==o2[0]) {	//같은 초밥일 경우
					return o1[1]-o2[1];		//손님 순서로 정렬
				}
				
				return o1[0]-o2[0];		//초밥 종류로 정렬
			}
		});
		
		for(int i=0; i<N; i++) {
			st=new StringTokenizer(br.readLine());
			int k=Integer.parseInt(st.nextToken());
			
			for(int j=0; j<k; j++) {
				customer.add(new int[] {Integer.parseInt(st.nextToken()), i});	//{초밥 종류, 손님 번호}	
			}
		}
		
		PriorityQueue<Integer> sushi=new PriorityQueue<>();
		
		st=new StringTokenizer(br.readLine());
		for(int i=0; i<M; i++) {
			sushi.add(Integer.parseInt(st.nextToken()));
		}
		
		int[] res=new int[N];
		
		while(!sushi.isEmpty()) {
			if(customer.isEmpty()) {
				break;
			}
			
			if(customer.peek()[0]==sushi.peek()) {
				sushi.poll();
				res[customer.poll()[1]]++;
			}
			else if(customer.peek()[0]>sushi.peek()) {
				sushi.poll();
			}
			else {
				customer.poll();
			}
		}
		
		StringBuilder sb=new StringBuilder();
		for(int i=0; i<N; i++) {
			sb.append(res[i]+" ");
		}
		
		System.out.println(sb);
	}
}