[백준 2831] 댄스 파티(JAVA)

링크

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

문제 설명

문제

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

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

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

문제 풀이

1. 배열리스트를 사용해 선호 이성 유형을 정리한다.
   a. 키 큰 여자를 선호하는 남자
   b. 키 작은 여자를 선호하는 여자
   c. 키 큰 남자를 선호하는 여자
   d. 키 작은 남자를 선호하는 여자
2. 입력을 받으며 쉬운 비교를 위해 위 예시의 a번과 c번을 0번 인덱스의 배열 리스트에 넣고, b번과 d번을 같은 1번 인덱스에 넣는다.
3. 각 배열리스트를 오름차순으로 정렬한다.
4. findPair 메서드를 사용해 0, 1번 타입의 커플을 찾는다.
   4-1. 타입에 맞게 큰 사람(tall)과 작은사람(small)을 각각의 배열리스트에서 뽑는다.
   4-2. 비교하며 tall > small 이라면 맞는 짝이므로 정답을 1증가시키고 각 인덱스를 1씩 증가시킴
   4-3. tall <= small이라면 큰 사람의 인덱스를 증가시키며 비교

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

public class Baek_2831_댄스파티 {
	static int N, pairs = 0; 
	static ArrayList<Integer>[] men = new ArrayList[2];
	static ArrayList<Integer>[] women = new ArrayList[2];
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());

		for(int i = 0; i < 2; i++) {
			men[i] = new ArrayList<Integer>();
			women[i] = new ArrayList<Integer>();
		}
		
		String[] menArr = br.readLine().split(" ");
		String[] womenArr = br.readLine().split(" ");
		for(int i = 0; i < N; i++) {
			int menHeight = Integer.parseInt(menArr[i]); 
			int womenHeight = Integer.parseInt(womenArr[i]); 

			if(menHeight < 0)
				men[0].add(menHeight*-1);
			else	
				men[1].add(menHeight);
			
			if(womenHeight < 0)
				women[1].add(womenHeight*-1);
			else	
				women[0].add(womenHeight);
		}
		
		for(int i = 0; i < 2; i++) {
			Collections.sort(men[i]);
			Collections.sort(women[i]);
		}
		
		findPair(0);
		findPair(1);
		
		System.out.println(pairs);
	}
	
	static void findPair(int type) {
		for(int i = 0, j = 0; i < men[type].size() && j < women[type].size();) {
           		//0번 타입 : 남자가 크고 여자가 작은 커플
           		//1번 타입 : 여자가 크고 남자가 작은 커플
			int tall = type == 0 ? men[type].get(i) : women[type].get(j);
			int small = type == 0 ? women[type].get(j) : men[type].get(i);
			
          		 //더 큰 쪽(남자 or 여자)의 index를 증가 시킴
			if(tall <= small) {
				if(type == 0)
					i++;
				else
					j++;
				continue;
			}
			
			pairs++;
			i++;
			j++;
		}
	}
}

GITHUB

https://github.com/hoonze/SSAFY_Algorithm_Study/tree/master/SSAFYT_Study/etc/2022.01/Baek_2831_%EB%8C%84%EC%8A%A4%ED%8C%8C%ED%8B%B0