[백준 2831] 댄스파티 - JAVA

문제 링크

문제 정의

• 남자와 여자의 수 $N$명 존재
• 남자와 여자의 키는 값으로 주어지고 선호도는 부호로 정해짐
  • 예시) -180은 내 키는 180이고 나보다 작은 사람을 선호한다는 의미
• 남녀 쌍을 선호도에 맞게 매칭 쌍의 최댓값을 구해라

접근 방법

1. 문제를 분리

가장 먼저 해야할 것은 가능한 쌍의 분리입니다.

우선 남자와 여자를 구분하는 것은 물론이고
선호도에 따라서도 분리해야 합니다.

즉 성별 내에서도
파트너가 나보다 큰 사람을 선호하는지,
작은 사람을 선호하는지
분리한다면 보다 쉽게 매칭을 수행할 수 있습니다.

2. 투 포인터

이 문제는 그리디하게
최대한 키 차이가 안나지만 선호도에 따라 쌍을 만들도록 해야 합니다.

그렇기 때문에
정렬해서 투포인터 형식으로 키 차이를 비교해가면서
쌍을 매칭시켜야 합니다.

투 포인터를 수행하기 위해
저는 정렬, 그리고 삭제까지 수행할 수 있는 우선순위 큐를 선택했습니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
	static StringTokenizer st;
	static PriorityQueue<Integer> manPlus;
	static PriorityQueue<Integer> manMinus;
	static PriorityQueue<Integer> womanPlus;
	static PriorityQueue<Integer> womanMinus;
	public static void main(String[] args) throws Exception {
		init();
		System.out.println(greedy());
	}

	private static int greedy() {
		int pair = 0;
		while (!manPlus.isEmpty() && !womanMinus.isEmpty()) {
			int man = manPlus.peek();
			int woman = womanMinus.peek();

			if (man < woman) {
				pair++;
				manPlus.poll();
				womanMinus.poll();
			}
			else {
				womanMinus.poll();
			}
		}

		while (!manMinus.isEmpty() && !womanPlus.isEmpty()) {
			int man = manMinus.peek();
			int woman = womanPlus.peek();

			if (man > woman) {
				pair++;
				manMinus.poll();
				womanPlus.poll();
			}
			else {
				manMinus.poll();
			}
		}

		return pair;
	}

	static void init() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		manPlus = new PriorityQueue<>();
		manMinus = new PriorityQueue<>();
		womanPlus = new PriorityQueue<>();
		womanMinus = new PriorityQueue<>();

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			int tall = Integer.parseInt(st.nextToken());
			if (tall > 0) {
				manPlus.offer(tall);
			}
			else {
				manMinus.offer(~tall + 1);
			}
		}

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			int tall = Integer.parseInt(st.nextToken());
			if (tall > 0) {
				womanPlus.offer(tall);
			}
			else {
				womanMinus.offer(~tall + 1);
			}
		}
	}
}