알고리즘 풀이(JAVA) - 백준 알고리즘_7568(브루트포스-덩치)

브루트포스(brute-force)

• 브루트포스란?
  brute는 “짐승같은, 난폭한”이라는 뜻이고, brute-force는 “난폭한 힘, 폭력”이라는 뜻이다. 암호학 용어로는 brute-force attack 또는 exhaustive key search, 우리말로는 노가다 또는 무차별 대입 공격이라 부른다. 주로 암호학에서도 쓰이는 방법이긴 하지만, 굳이 암호학만의 문제는 아니고 다른 알고리즘 분야에서도 사용되고 있다. 간단하게 말하자면 노가다와 다굴을 논리적이고 과학적으로 하는 방식.

• 특징
  조합 가능한 모든 문자열을 하나씩 대입해 보는 방식으로 문제를 푸는 것인데, 얼핏 무식하다고 생각할 수도 있겠지만 성공한다는 가정 하에 항상 정확도 100%를 보장한다는 점에서, 자원만 충분하면 가장 무서운 방법이다. 이론적으로 가능한 모든 경우의 수를 다 검색해 보는 것이라 정확도 100%가 항상 보장되니, 암호학에서는 가장 확실한 방법으로 통용되고 있다. 무엇보다도 암호 확인 작업이라는 것이 손으로 입력한 문자열의 동일 여부를 확인하는 것이기 때문에, 가능한 경우를 하나씩 대입하다 보면 언젠가는 암호를 찾을 수 있게 되는 식이다. 다만 정말로 그냥 무식하게 때려박는 건 아니고, 숫자만 섞어서 대입해보기 한번, 로마자만 섞어서 대입해보기 한번 이런식으로 하다가 안되면 나머지를 순차적으로 하는 식으로 특정 규칙에 따라 우선순위를 두고 하기도 한다.

문제

문제 링크 : https://www.acmicpc.net/problem/7568

우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다.
어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x,y)로 표시된다.
두 사람 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명의 집단에서 각 사람의 덩치 등수는 자신보다 더 “큰 덩치”의 사람의 수로 정해진다.
만일 자신보다 더 큰 덩치의 사람이 k명이라면 그 사람의 덩치 등수는 k+1이 된다.
이렇게 등수를 결정하면 같은 덩치 등수를 가진 사람은 여러 명도 가능하다.
아래는 5명으로 이루어진 집단에서 각 사람의 덩치와 그 등수가 표시된 표이다.

위 표에서 C보다 더 큰 덩치의 사람이 없으므로 C는 1등이 된다. 그리고 A, B, D 각각의 덩치보다 큰 사람은 C뿐이므로 이들은 모두 2등이 된다.
그리고 E보다 큰 덩치는 A, B, C, D 이렇게 4명이므로 E의 덩치는 5등이 된다. 위 경우에 3등과 4등은 존재하지 않는다.
여러분은 학생 N명의 몸무게와 키가 담긴 입력을 읽어서 각 사람의 덩치 등수를 계산하여 출력해야 한다.

풀이

• 입력된 정보 배열 생성(String[] members)
• 배열을 순환 하며 자신 보다 몸무게&키 가 큰 인원의 카운트를 센다.(compare)

소스

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Baekjoon_7568 {
	public static void main(String[] args){
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        try{
        	int N = Integer.parseInt(reader.readLine());
        	String[] members = new String[N];
        	for(int i = 0; i < N; i++) {
        		members[i] = reader.readLine();
        	}
        	//등급 배열 생성
        	int[] grade = grade(members);
        	//출력
        	print(grade);
        }catch(Exception e){
            e.printStackTrace();
        }
    }

	//등급
	private static int[] grade(String[] members) {
		int[] grade = new int[members.length];
		for(int i = 0; i < members.length; i++) {
			String[] member = members[i].split(" ");
			int weight = Integer.parseInt(member[0]);
			int height = Integer.parseInt(member[1]);
			
			grade[i] = compare(members, weight, height);
		}
		return grade;
	}

	//덩치 비교
	private static int compare(String[] members, int weightA, int heightA) {
		int cnt = 1;
		for (int j = 0; j < members.length; j++) {
			String[] tmpMember = members[j].split(" ");
			int weightB = Integer.parseInt(tmpMember[0]);
			int heightB = Integer.parseInt(tmpMember[1]);	
			if(weightA < weightB && heightA < heightB) {
				cnt++;
			}
		}
		return cnt;
	}
	
	private static void print(int[] grade) {
		for(int i = 0; i < grade.length; i++) {
			System.out.print(grade[i]);
			System.out.print(" ");
		}
	}
}