[백준] 7568번 : 덩치 - JAVA [자바]

www.acmicpc.net/problem/7568

 

7568번: 덩치

우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x,y)로 표시된다. 두 사람 A 와 B의 덩�

www.acmicpc.net

 

---

• 문제

 

 

 

매우 간단한 문제다!

 

 

※ 주의할 점

1. 키와 몸무게가 모두 클 때에만 '덩치가 크다' 라고 정의하고 있다.

 

 

 

 

---

• 알고리즘 [접근 방법]

 

 

이번에도 역시 브루트포스를 이용하여 푸는 문제다.

 

먼저 문제를 보면 '덩치가 크다'는 기준은 키와 몸무게가 모두 비교하려는 대상보다 클 때이다.

즉, 어느 한 쪽이라도 만족 못할 경우 덩치가 크다고 할 수 없다.

 

 

그럼 브루트포스로 어떻게 풀 수 있을까?

 

 

일단 키와 몸무게를 담는 2차원 배열을 생성한 뒤,

이중 반복문을 통해 각 배열의 인덱스를 모두 탐색하는 방법이다.

 

이때 각 비교되는 두 인덱스의 각각의 키와 몸무게를 비교하여 랭크를 지정해주는 방식이다.

 

좀 더 상세하게 말하자면

rank = 1 부터 시작하여 해당 사람보다 덩치가 큰 사람이 있을 경우 해당 사람은 순위는 뒤로 밀리기 때문에 rank 값을 증가시키는 것이다.

이렇게 자기 자신을 제외한 나머지 사람들을 모두 비교하여 rank 값을 출력하면 된다.

 

만약 자기보다 덩치가 큰 사람이 없을 경우 rank 는 1 이 될 것이고, 덩치가 큰 사람이 K 명 있을 경우 rank + K 가 자신의 랭크(순위)가 될 것이다.

 

즉, 기본적인 알고리즘은 다음과 같다.

 

int[][] arr = new int[N][2]; 
 
// 입력
for(int i = 0; i < N; i++) {
	arr[i][0] = input();	// [i][0] : 몸무게
	arr[i][1] = input();	// [i][1] : 키
}
		
for(int i = 0; i < N; i++) {
	int rank = 1;	// rank 는 1 부터 시작
			
	for(int j = 0; j < N; j++) {
		if(i == j) continue;	// 같은 사람은 비교할 필요가 없음
 
		/* 
		i 번째 사람과 j 번째 사람을 비교하여 i 가 j 보다
		덩치가 작을 경우 rank 값을 1 증가시킨다
		*/
		if (arr[i][0] < arr[j][0] && arr[i][1] < arr[j][1]) {
			rank++;
		}
	}
 
	// i 의 랭크값을 출력
	print(rank + " ");
 
}

 

 

 

 

 

 

 

 

---

• 3가지 방법을 이용하여 풀이한다.

 

알고리즘은 앞서 설명 한 것을 그대로 적용 할 것이다.

다만, 입력 방법을 달리하여 Scanner 와 BufferedReader 을 사용하여 풀 것이다.

 

마지막으로 출력 부분에서 매 반복문마다 출력하는 방식이 아닌 StringBuilder 을 사용하여 하나의 문자열로 이어준 뒤, 한 번에 출력해보는 방식을 사용해보려 한다.

 

위 3가지 입출력 방법을 통해 각각의 성능을 비교해보려 한다.

 

---

• 풀이

- 방법 1 

 

import java.util.Scanner;
 
public class Main {
	public static void main(String[] args) {
 
		Scanner in = new Scanner(System.in);
 
		int N = in.nextInt();
 
		int[][] arr = new int[N][2];
 
		for(int i = 0; i < N; i++) {
			arr[i][0] = in.nextInt();	// [i][0] : 몸무게 
			arr[i][1] = in.nextInt();	// [i][1] : 키 
		}
		
		
		for(int i = 0; i < N; i++) {
			int rank = 1;
			
			for(int j = 0; j < N; j++) {
				if(i == j) continue;
				if (arr[i][0] < arr[j][0] && arr[i][1] < arr[j][1]) {
					rank++;
				}
			}
 
			System.out.print(rank + " ");
		}
 
	}
}

 

 

가장 기본적인 방법이다.

 

다행이 입력되는 케이스(N)의 최대 개수가 50까지 밖에 안되기 때문에 시간초과가 날 가능성은 매우 적다.

 

 

 

---

- 방법 2 

 

 

Scanner 대신 BufferedReader 로 입력받는 방법이다.

필자의 다른 포스팅들을 보면 알겠지만, 기본적으로 BufferedReader 입력방식이 좋다는 것을 볼 수 있으니 참고하시길 바란다.

 

그리고 BufferedReader 의 경우 readLine() 입력메소드가 한 줄을 통째로 읽기 때문에 문자열 분리를 해주어야 한다.

이번의 경우 StringTokenizer 가 아닌 split() 메소드를 사용해보기로 한다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
 
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];
 
		String[] sp;
		for(int i = 0; i < N; i++) {
			sp = br.readLine().split(" ");			// 문자열 분리
			arr[i][0] = Integer.parseInt(sp[0]);	// [i][0] : 몸무게 
			arr[i][1] = Integer.parseInt(sp[1]);	// [i][1] : 키 
		}
		
				
		for(int i = 0; i < N; i++) {
			int rank = 1;
			
			for(int j = 0; j < N; j++) {
				if(i == j) continue;
				if (arr[i][0] < arr[j][0] && arr[i][1] < arr[j][1]) {
					rank++;
				}
			}
 
			System.out.print(rank + " ");
		}
 
	}
}

 

 

---

- 방법 3 

 

 

이번 문제는 워낙 케이스가 적어서 최대 출력 개수가 50개 밖에 안되기 때문에 성능이 매우 차이난다고 할 수는 없다.

그러나 다른 문제들을 풀어보면 알겠지만 출력의 반복 횟수가 많아질 수록 StringBuilder 을 통해 출력 문구들을 하나로 묶어 마지막에 한 번에 출력하는게 성능이 월등히 좋아진다.

 

(물론 StringBuilder 대신 BufferedWriter 을 사용해도 된다)

 

또한 입력방법은 직전 코드와 같이 BufferedReader 을 쓴다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
 
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];
 
		String[] str;
		for(int i = 0; i < N; i++) {
			str = br.readLine().split(" ");
			arr[i][0] = Integer.parseInt(str[0]);	// [i][0] : 몸무게 
			arr[i][1] = Integer.parseInt(str[1]);	// [i][1] : 키 
		}
			
		StringBuilder sb = new StringBuilder();
		
		for(int i = 0; i < N; i++) {
			int rank = 1;
			
			for(int j = 0; j < N; j++) {
				if(i == j) continue;
				if (arr[i][0] < arr[j][0] && arr[i][1] < arr[j][1]) {
					rank++;
				}
			}
 
			sb.append(rank).append(' ');
		}
		System.out.println(sb);
	}
}

 

 

 

 

 

 

 

 

 

 

 

---

• 성능

 

위에서 부터 순서대로

 

채점 번호 : 19939338  -  방법 3 : BufferedReader + StringBuilder

채점 번호 : 19939253  -  방법 2 : BufferedReader 

채점 번호 : 19939243  -  방법 1 : Scanner

 

 

입력의 경우는 확실히 Scanner 보다는 BufferedReader 가 빠른 걸 볼 수 있다.

출력 부분에서는 그리 차이는 안나는듯 하다.. (워낙 출력할 케이스가 적어서..)

 

 

 

 

 

---

• 정리

 

이 문제는 크게 설명할 내용이 없을 정도로 매우 쉬운 문제다.

(문제 출처를 보니 초등부 문제더라...)

 

또한 브루트포스 알고리즘 자체가 완전탐색만 하면 되기 때문에 구현하는 것도 크게 어려운 부분은 없을 것이다.

불필요한 탐색을 줄이는 방법을 고민하는 것이 이번 카테고리의 가장 중요한 포인트가 될 것이다.