백준 5587 - 카드 캡터 상근(Java)

www.acmicpc.net/problem/5587

5587번: 카드 캡터 상근이

1. 유형

구현

 

2. 자료구조

우선순위큐

 

3. 기능

- 상근카드, 근상카드 나누기

- 타겟카드 보다 큰지 작은지 판단하는 함수

 

4. 풀이

 

조건에서 가장 작은 카드부터 출력해야하기 때문에 우선순위큐를 선언

그 다음은 큐에서 하나씩 수를 빼와서 타깃과 비교하면 끝.

 

코드.

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

public class Main {
	static int N, target;
	static PriorityQueue<Integer> fir,sec;
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		N = Integer.valueOf(st.nextToken());
		fir = new PriorityQueue<>();
		sec = new PriorityQueue<>();
		boolean check[] = new boolean[2*N+1];
		for(int i=0; i<N ;i++) {
			st = new StringTokenizer(in.readLine());
			int k= Integer.valueOf(st.nextToken());
			check[k] = true;
			fir.add(k);
		}
		for(int i=1; i<2*N+1; i++) {
			if(!check[i]) {
				sec.add(i);
			}
		}
		int turn = 0;
		target = 0;
		while(!fir.isEmpty() && !sec.isEmpty()) {
			if(turn == 0) {//상근턴
				sol(fir);
			}else {//근상턴
				sol(sec);
			}
			++turn;
			turn%=2;
		}
		System.out.println(sec.size());
		System.out.println(fir.size());
	}
	static void sol(PriorityQueue<Integer> pq) {
		PriorityQueue<Integer> tmp = new PriorityQueue<>();
		boolean flag = false;
		while(!pq.isEmpty()) {
			int k = pq.poll();
			if(target < k) {
				target = k;
				flag = true;
				break;
			}else {
				tmp.add(k);
			}
		}
		while(!tmp.isEmpty()){
			pq.add(tmp.poll());
		}
		if(!flag) {
			target = 0;
		}
	}
}

5. 느낀점

문제가 어려운건 아니지만 이해하는데 시간이 좀 걸렸다.