문제
현수는 씨름 감독입니다. 현수는 씨름 선수를 선발공고를 냈고, N명의 지원자가 지원을 했습니다.
현수는 각 지원자의 키와 몸무게 정보를 알고 있습니다.
현수는 씨름 선수 선발 원칙을 다음과 같이 정했습니다.
“A라는 지원자를 다른 모든 지원자와 일대일 비교해서 키와 몸무게 모두 A지원자 보다 높은(크고, 무겁다) 지원자가
존재하면 A지원자는 탈락하고, 그렇지 않으면 선발된다.”
N명의 지원자가 주어지면 위의 선발원칙으로 최대 몇 명의 선수를 선발할 수 있는지 알아내는 프로그램을 작성하세요.
입력
첫째 줄에 지원자의 수 N(5<=N<=30,000)이 주어집니다.
두 번째 줄부터 N명의 흰돌 능력치와 검은돌 능력치 정보가 차례로 주어집니다.
각 선수의 흰돌능력치가 모두 다르고, 검은돌 능력치도 모두 다릅니다. 능력치 값은 1,000,000이하의 자연수입니다.
코드
public class Ssireum {
public static void main(String[] args) {
Scanner in=new Scanner(System.in);
int input1 = in.nextInt();
int[] cm = new int[input1];
int[] kg = new int[input1];
for(int i=0; i<input1; i++){
cm[i] = in.nextInt();
kg[i] = in.nextInt();
}
int solution = solution(cm, kg, input1);
System.out.println(solution);
}
public static int solution(int[] cm, int[] kg, int input1){
int result = input1;
for(int i=0; i<input1; i++){ //기준
for(int j=0; j<input1; j++){ //비교
if(cm[i]<cm[j]){
if(kg[i]<kg[j]){
result--;
break;
}
}
}
}
return result;
}
}시간 복잡도 다 쓰는 풀이방식
public class Ssireum {
public static void main(String[] args) {
Scanner in=new Scanner(System.in);
int input1 = in.nextInt();
ArrayList<Body> list = new ArrayList<>();
for(int i=0; i<input1; i++){
Body body = new Body(in.nextInt(), in.nextInt());
list.add(body);
}
Collections.sort(list);
int result = solution(list);
System.out.println(result);
}
private static int solution(ArrayList<Body> list) {
int cnt = 0;
int max = Integer.MIN_VALUE;
for(Body b : list){
if(b.kg > max){
max = b.kg;
cnt++;
}
}
return cnt;
}
static class Body implements Comparable<Body>{
public int cm;
public int kg;
public Body(int cm, int kg) {
this.cm = cm;
this.kg = kg;
}
@Override
public int compareTo(Body o) {
return o.cm - this.cm;
}
}
}문제에서 요구하는 풀이방식
설명
첫번째 문제 풀이 방식은 선형 탐색이라고 할수 있다. 키와 몸무게 값을 각각의 배열에 집어넣어 모두 비교하는 형식인데 시간 복잡도를 조금이라도 줄이기 위해 break를 두었다. 최악의 경우 O(N^2)의 복잡도로 문제를 풀어내기 때문에 잘못된 풀이 방식이다.
두번째 문제 풀이 방식은 class의 comparable을 활용하여 list에 객체를 담고 한번의 sort로 키순으로 모두 나열한 후 몸무게만 비교하여 결과를 반환하는 방식이다. 이 경우 O(N)의 시간 복잡도로 문제를 풀어내게 되어 첫번째 방법보다 훨씬 성능이 좋다.
greedy 알고리즘의 가장 기초적인 문제였다. 앞으로도 comparator와 comparable을 사용하여 문제를 풀어보자
