[백준 - 2831][GOLD 4][해설 X] - 댄스 파티 (JAVA)

문제 링크

---

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

 

문제

---

남자 N명과 여자 N명이 상근이가 주최한 댄스 파티에 왔다. 상근이는 모든 사람의 키를 알고있다. 각 남자는 모두 여자와 춤을 출 수 있고, 여자는 남자와 춤을 출 수 있다. 모든 사람은 많아야 한 사람과 춤을 출 수 있다.

모든 남자는 자신이 선호하는 여자와 춤을 추려고 한다. 각 남자가 선호하는 여자는 두 가지 유형이 있는데, 한 유형은 자신보다 키가 큰 여자이고, 다른 유형은 자신보다 키가 작은 유형이다. 여자도 남자와 마찬가지로 자신이 선호하는 남자와 춤을 추려고 한다. 각 여자가 선호하는 남자도 남자와 비슷하게 두 유형이 있다. (자신보다 키가 큰 남자, 작은 남자) 키가 같은 남자와 여자가 춤을 추는 일은 일어나지 않는다.

이때, 상근이는 각 사람의 키와 선호하는 이성 유형을 알고 있다. 이런 조건을 가지고 춤을 출 쌍을 만들어 주려고 한다. 상근이는 최대 몇 쌍을 만들 수 있을까?

 

입력

---

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100,000)

둘째 줄에는 남자의 키가 밀리미터 단위로 주어진다. 키는 절댓값이 1500보다 크거나 같고, 2500보다 작거나 같은 정수이다. 사람의 키는 주어지는 값의 절댓값이다. 키가 양수인 경우에는 자신보다 키가 큰 여자와 춤을 추기를 원하는 남자이고, 음수인 경우에는 키가 작은 사람과 춤을 추기를 원하는 남자이다.

셋째 줄에는 여자의 키가 밀리미터 단위로 주어진다. 키의 범위나 의미 역시 남자와 동일하다. 

 

출력

---

첫째 줄에 상근이가 만들어 줄 수 있는 쌍의 최댓값을 출력한다.

 

해결 코드

---

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());

        PriorityQueue<Integer> findSmallerWomanQ = new PriorityQueue<>(Collections.reverseOrder());
        PriorityQueue<Integer> findTallerWomanQ = new PriorityQueue<>();
        PriorityQueue<Integer> findSmallerManQ = new PriorityQueue<>(Collections.reverseOrder());
        PriorityQueue<Integer> findTallerManQ = new PriorityQueue<>();

        st = new StringTokenizer(br.readLine());


        for(int i=0;i<N;i++){
            int height = Integer.parseInt(st.nextToken());

            if(height < 0){
                findSmallerWomanQ.add(height);
            }else{
                findTallerWomanQ.add(height);
            }
        }

        st = new StringTokenizer(br.readLine());

        for(int i=0;i<N;i++){
            int height = Integer.parseInt(st.nextToken());

            if(height < 0){
                findSmallerManQ.add(height);
            }else{
                findTallerManQ.add(height);
            }
        }

        int count = 0;

        //키 작은 여성을 원하는 남성과 키가 큰 남성을 원하는 여성간 조합 찾기
        while(!findSmallerWomanQ.isEmpty()){
            int availableMaxHeight = Math.abs(findSmallerWomanQ.poll()) - 1;

            //다음 여성이 원하는 남성 키는 현재 원하는 남성 키보다 크므로 현재 남성은 원하는 짝을 만들 수 없다.
            if(!findTallerManQ.isEmpty() && findTallerManQ.peek() <= availableMaxHeight){
                findTallerManQ.poll();
                count++;
            }
        }

        //키가 큰 여성을 원하는 남성과 키가 작은 남성을 원하는 여성간 짝 찾기
        while(!findSmallerManQ.isEmpty()){
            int availableMaxHeight = Math.abs(findSmallerManQ.poll()) - 1;

            //다음 남성이 원하는 여성 키는 현재 원하는 여성 키보다 크므로 현재 여성은 원하는 짝을 만들 수 없다.
            if(!findTallerWomanQ.isEmpty() && findTallerWomanQ.peek() <= availableMaxHeight){
                findTallerWomanQ.poll();
                count++;
            }
        }

        System.out.println(count);
    }
}

 

 

실행 결과

---

 

팁

---

• 서로 다른 범위가 있다면 정렬된 큐도 다르게 나누자
• 큐가 정렬되어 있을 때 가장 작은 값도 만족시키지 못하면 그 다음도 만족시키지 못하는 것을 이용하자