백준 2831 댄스파티

 

https://www.acmicpc.net/problem/2831

2831번: 댄스 파티

 

1. 기본 조건

- 키가 -인 남자(자기보다 키가 작은 여자를 원하는 남자) 는 항상 키가 + 인여자(자기보다 키가 큰 남자를 원하는 여자)와 매칭된다.

- 키가 + 인 남자, 키가 -인 여자도 마찬가지 이유로 서로 매칭된다.

 

2. 또한, 커플쌍을 최대로 하기 위해서는

키가 + 인 여자는 자기보다 키가 큰 남자중 가장 작은 남자와 매칭되야한다.

 

예제를 통해 알아보자

 

7
-1900 -2000 -2500 1500 1600 2500 -2500  //남자
1700 1800 2200 -1550 2100 -2500 -1700 //여자

 

이중에서 남자 (-) 여자 (+)인경우만 그림으로 표현하면 다음과 같다.

-  1700여는 -1900 -2000 -2500 -2500인 남자를 모두 만날수있지만, 최대 쌍을 만드는건 1700여자가 1900인 남자와 이어지는 경우이다 즉, 자기보다 키가 큰 남자 중 가장 작은 남자를 선택하는 것이다.(이를 다른말로 upper_bound라고도 부른다.) 그 이유는 자명하다. 1700이 여자중에서 키가 제일 작기 때문에, 다른 여자들보다 항상 선택권이 많거나 같기 때문이다. 즉 다른 여자들이 자기보다 키가 작아서 못 고를수도 있는 가능성이 있는 남자를 고르는 것이다.

 

- 1800입장에서도 가장 최대의 경우는 자기보다 키가 큰 남자중 가장 작은 남자 1900을 고르는 것이 최대경우지만

앞의 1700이 먼저 1900을 골랐기 때문에 2000을 골라야한다. 즉, 중복되는 선택을 막기 위해서 원소를 삭제하거나 방문처리를 해야한다.

 

위 두 가지 조건 모두를 만족하는 자료구조는 우선순위큐다.

우선순위큐는 upperbound를 구할수 있는 순서가 있는 자료구조이며, 삭제가 O(logN)시간에 이루어진다.(JAVA의 ArrayList나 C++의 vector 삭제에 O(N)시간이 걸리기 때문에 시간초과가 발생한다.)

 

알고리즘은 다음과 같다.

while(!b0.isEmpty()&&!g1.isEmpty()) { //b0 는 자기보다 작은 g1를 만나고 싶어하는 상황
    int b = b0.poll();
    int g =g1.peek();
    if(g<b) {
    	answer++;
		g1.poll();
	}
}

1. b의 앞원소와 g의 앞원소를 비교한다.

2-1 b>g이면 가능한 경우수이므로 answer 증가 g와b의 앞원소 제거

2-2 아니면 b의 앞원소만 제거

3. b0,g1 둘중하나가 비기 전까지반복

 

반대경우에도 똑같이 적용하면된다.

 

import java.util.*;
import java.io.*;

public class Main{
	public static class MyScanner {
		BufferedReader bf;
		StringTokenizer st;

		MyScanner() {
			bf = new BufferedReader(new InputStreamReader(System.in));
		}

		String next() {
			while (st == null || !st.hasMoreTokens()) {
				try {
					st = new StringTokenizer(bf.readLine());
				} catch (Exception e) {
					e.printStackTrace();
				}

			}
			return st.nextToken();
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}

		public long nextLong() {
			return Long.parseLong(next());
		}
	}

	public static void main(String[] args) {
		MyScanner sc = new MyScanner();
		int N = sc.nextInt();

		PriorityQueue<Integer> g1 = new PriorityQueue<Integer>();
		PriorityQueue<Integer> g0 = new PriorityQueue<Integer>();
		PriorityQueue<Integer> b1 = new PriorityQueue<Integer>();
		PriorityQueue<Integer> b0 = new PriorityQueue<Integer>();

		for (int i = 0; i < N; i++) {
			int x = sc.nextInt();
			if (x < 0)
				b0.add(-x);
			else
				b1.add(x);
		}

		for (int i = 0; i < N; i++) {
			int x = sc.nextInt();
			if (x < 0)
				g0.add(-x);
			else
				g1.add(x);
		}

		int answer = 0;

		while (!b0.isEmpty() && !g1.isEmpty()) { // b0 는 자기뵈다 작은 g 만나고 싶어함
			int b = b0.poll();
			int g = 987654321;
			g = g1.peek();
			if (g < b) {
				answer++;
				g1.poll();
			}
		}
		while (!g0.isEmpty() && !b1.isEmpty()) { // b0 는 자기뵈다 작은 g 만나고 싶어함
			int g = g0.poll();
			int b = b1.peek();
			if (g > b) {
				answer++;
				b1.poll();
			}
		}
		System.out.println(answer);

	}

}

 

P.S ArrayList로 처음에 풀다가 삭제하는 부분때문에 계속 시간초과나서 우선순위큐로 바꿨음