[백준/Java]Q7568

백준 알고리즘 11단계 브루트 포스 7568번 문제입니다.

---

Q. 덩치 구하기
두 사람 A 와 B의 덩치가 각각 (x, y), (p, q)라고 할 때 x > p 그리고 y > q 이라면 우리는 A의 덩치가 B의 덩치보다 "더 크다"고 말한다.
예를 들어 어떤 A, B 두 사람의 덩치가 각각 (56, 177), (45, 165)라고 한다면 A의 덩치가 B보다 큰 셈이 된다. 그런데 서로 다른 덩치끼리 크기를 정할 수 없는 경우도 있다.
예를 들어 두 사람 C와 D의 덩치가 각각 (45, 181), (55, 173)이라면 몸무게는 D가 C보다 더 무겁고, 키는 C가 더 크므로, "덩치"로만 볼 때 C와 D는 누구도 상대방보다 더 크다고 말할 수 없다.
학생 N명의 몸무게와 키가 담긴 입력을 읽어서 각 사람의 덩치 등수를 계산하여 출력해야 한다.
N명의 집단에서 각 사람의 덩치 등수는 자신보다 더 "큰 덩치"의 사람의 수로 정해진다.
만일 자신보다 더 큰 덩치의 사람이 k명이라면 그 사람의 덩치 등수는 k+1이 된다. 이렇게 등수를 결정하면 같은 덩치 등수를 가진 사람은 여러 명도 가능하다.

[입력]
- 첫 줄에는 전체 사람의 수 N이 주어진다. 그리고 이어지는 N개의 줄에는 각 사람의 몸무게와 키를 나타내는 양의 정수 x와 y가 하나의 공백을 두고 각각 나타난다.

 

[조건]

- 나열된 사람의 덩치 등수를 구해서 그 순서대로 첫 줄에 출력해야 한다. 단, 각 덩치 등수는 공백문자로 분리되어야 한다.

풀이

이어지는 문제 역시 브루트 포스 문제로 이중 for문과 이중 배열을 이용했다.

배열의 0번째 인덱스에는 몸무게를 1번째 인덱스에는 키를 2번째 인덱스에는 등수를 저장시켰다.

[n][0] = 몸무게
[n][1] = 키

[n][2] = 등수

 

등수를 정하는 조건은 키와 몸무게가 자신보다 큰 사람이 몇 명이 있느냐(키나 몸무게가 아닌 두 조건이 일치할 때)의 따라 정해진다. 따라서 아래와 같이 각 사람의 몸무게와 키를 입력받을 때, A부터 E까지 자신을 제외한 다른 사람과 비교를 하면서 카운트를 센다면 답을 구할 수 있다.
A (55, 185) -> 2(C)
B (58, 183) -> 2(C)
C (88, 186) -> 1( )
D (60, 175) -> 2(C)
E (46, 155) -> 5(A, B, C, D)

 

소스

package com.baek.algo.step11;

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

public class Q7568 {

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(bf.readLine());
		int[][] p = new int[n][3];
		int k   = 1;
		int cnt = 0;
        
		for(int i = 0; i < n; i++) {
			StringTokenizer st  = new StringTokenizer(bf.readLine(), " ");

			for(int j = 0; j < 2; j++) {
				p[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		for(int i = 0; i < n; i++) {
			int weight1 = p[i][0];
			int height1 = p[i][1];

			for(int j = 0; j < n; j++) {
				if(i != j) {
					int weight2 = p[j][0];
					int height2 = p[j][1];

					if(weight1 < weight2 && height1 < height2) {
						cnt = cnt + 1;
					}
				}
			}

			p[i][2] = k + cnt;
			cnt = 0;
			System.out.print(p[i][2] + " ");
		}

		bf.close();
	}
}