[백준] 7568.덩치(Java8)

 문제 

 풀이 

package Implementation;

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

public class Main {

	public static void main(String[] args) throws IOException{
		//덩치
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());//전체 사람의 수
		int[][] arr = new int[n][2];
		StringTokenizer st;
		int[] answer = new int[n];//정답
		
		//키와 몸무게 입력받기
		for(int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			arr[i][0] = Integer.parseInt(st.nextToken());
			arr[i][1] = Integer.parseInt(st.nextToken());
			answer[i] = 1;
		}
		
		//등수 계산하기
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				if(i == j) {
					//같은 사람은 비교X
					continue;
				}
				if(arr[i][0] < arr[j][0] && arr[i][1] < arr[j][1]) {
					//i가 j보다 덩치가 작을 경우 등수 증가
					answer[i]++;
				}
			}
		}
		
		StringBuilder sb = new StringBuilder();
		for(int ans : answer) {
			sb.append(ans).append(" ");
		}
		
		System.out.println(sb);
		br.close();

	}

}

 팁 

1. 부르트포스(brute force) 알고리즘

• 해당 문제는 부르트 포스 알고리즘을 활용하여 풀 수 있다.
• brute: 무식한, force: 힘   무식한 힘으로 해석할 수 있다.
• 완전탐색 알고리즘. 즉, 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만을 가져온다.
  - 선형 구조를 전체적으로 탐색하는 순차 탐색, 비선형 구조를 전체적으로 탐색하는 깊이 우선 탐색(DFS, Depth First Search)과 너비 우선 탐색(BFS, breadth first search)이 가장 기본적인 도구이다.

2. 덩치가 크다

• 두 사람 A 와 B의 덩치가 각각 (x, y), (p, q)라고 할 때 x > p 그리고 y > q 이라면 우리는 A의 덩치가 B의 덩치보다 "더 크다"고 말한다.

=> 키와 몸무게를 2차원 배열로 입력받은 후, 이중 for문을 통해 각 배열의 인덱스를 모두 탐색한다.

3. 자기 자신보다 덩치가 큰 사람이 존재하는 경우 순위가 밀린다.

• 자신보다 덩치가 큰 사람이 없을 경우, 등수는 1이다.
• 반면에 자신보다 덩치가 큰 사람이 n명 존재한다면, 등수는 1 + n 이다. 

for(int i = 0; i < n; i++) {                                
	for(int j = 0; j < n; j++) {                            
		if(i == j) {                                        
			//같은 사람은 비교X                                    
			continue;                                       
		}                                                   
		if(arr[i][0] < arr[j][0] && arr[i][1] < arr[j][1]) {
			//i가 j보다 덩치가 작을 경우 등수 증가                        
			answer[i]++;                                    
		}                                                   
	}                                                       
}​

 출처 

7568번: 덩치