728x90
반응형
▷ 문제
현수는 씨름 감독입니다. 현수는 씨름 선수를 선발공고를 냈고, N명의 지원자가 지원을 했습니다.
현수는 각 지원자의 키와 몸무게 정보를 알고 있습니다.
현수는 씨름 선수 선발 원칙을 다음과 같이 정했습니다.
“A라는 지원자를 다른 모든 지원자와 일대일 비교해서 키와 몸무게 모두 A지원자 보다 높은(크고, 무겁다) 지원자가
존재하면 A지원자는 탈락하고, 그렇지 않으면 선발된다.”
N명의 지원자가 주어지면 위의 선발원칙으로 최대 몇 명의 선수를 선발할 수 있는지 알아내는 프로그램을 작성하세요.
* 입력
첫째 줄에 지원자의 수 N(5<=N<=30,000)이 주어집니다.
두 번째 줄부터 N명의 키와 몸무게 차례로 주어집니다.
각 선수의 키가 모두 다르고, 몸무게도 모두 다릅니다. 몸무게 값은 1,000,000이하의 자연수입니다.
* 출력
첫째 줄에 씨름 선수로 뽑히는 최대 인원을 출력하세요.
▷ 입력 예시
5
172 67
183 65
180 70
170 72
181 60
▷ 출력 예시
3
▷ 풀이
1. Scanner 클래스 사용
import java.util.*;
class Body implements Comparable<Body>{
public int h, w;
Body(int h, int w) {
this.h = h;
this.w = w;
}
@Override
public int compareTo(Body o){
return o.h - this.h;
}
}
public class Main {
public int solution(ArrayList<Body> arr, int n) {
int cnt = 0;
Collections.sort(arr); // 키 내림차순 정렬
int max = Integer.MIN_VALUE;
for(Body ob : arr){
/*
키는 이미 내림차순 정렬되어있으며 max는 자신보다 앞의 인원들의
몸무게의 최댓값이므로 선택된 ob의 몸무게는 max보다 커야한다.
*/
if(ob.w > max){
max = ob.w;
cnt++;
}
}
return cnt;
}
public static void main(String[] args) {
Main main = new Main();
Scanner kb = new Scanner(System.in);
int n = kb.nextInt();
ArrayList<Body> arr = new ArrayList<>();
for(int i=0; i<n; i++){
int h = kb.nextInt();
int w = kb.nextInt();
arr.add(new Body(h, w));
}
kb.close();
System.out.println(main.solution(arr, n));
}
}2. BufferedReader 클래스 사용
import java.util.*;
import java.io.*;
class Body implements Comparable<Body>{
public int h, w;
Body(int h, int w) {
this.h = h;
this.w = w;
}
@Override
public int compareTo(Body o){
return o.h - this.h;
}
}
public class Main {
public int solution(ArrayList<Body> arr, int n) {
int cnt = 0;
Collections.sort(arr); // 키 내림차순 정렬
int max = Integer.MIN_VALUE;
for(Body ob : arr){
/*
키는 이미 내림차순 정렬되어있으며 max는 자신보다 앞의 인원들의
몸무게의 최댓값이므로 선택된 ob의 몸무게는 max보다 커야한다.
*/
if(ob.w > max){
max = ob.w;
cnt++;
}
}
return cnt;
}
public static void main(String[] args) throws IOException {
Main main = new Main();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(br.readLine());
ArrayList<Body> arr = new ArrayList<>();
for(int i=0; i<n; i++){
st = new StringTokenizer(br.readLine());
int h = Integer.parseInt(st.nextToken());
int w = Integer.parseInt(st.nextToken());
arr.add(new Body(h, w));
}
System.out.println(main.solution(arr, n));
}
}▷ 메모
- 입력문을 받아 정렬할 수 있는 클래스를 따로 만드는 것이 핵심이다.
- 키를 역순으로 정렬한 뒤 본인의 몸무게가 본인보다 키가 큰 멤버들의 몸무게보다 클 경우 선발된다는 점을 이용한다.
- 입력을 받을 때 Scanner 클래스를 사용했을 경우 162ms, BufferedReader를 사용했을 경우 120ms가 소요되었으며 또한 메모리도 1mb 단축되었다.
반응형
