인프런 9-1. 씨름선수 (자바)

[문제]

현수는 씨름 감독입니다. 현수는 씨름 선수를 선발공고를 냈고, N명의 지원자가 지원을 했습니다.
현수는 각 지원자의 키와 몸무게 정보를 알고 있습니다.
현수는 씨름 선수 선발 원칙을 다음과 같이 정했습니다.
“A라는 지원자를 다른 모든 지원자와 일대일 비교해서 키와 몸무게 모두 A지원자 보다 높은(크고, 무겁다) 지원자가 존재하면 A지원자는 탈락하고, 그렇지 않으면 선발된다.”
N명의 지원자가 주어지면 위의 선발원칙으로 최대 몇 명의 선수를 선발할 수 있는지 알아내는 프로그램을 작성하세요.


[입력]

첫째 줄에 지원자의 수 N(5<=N<=30,000)이 주어집니다.
두 번째 줄부터 N명의 키와 몸무게 정보가 차례로 주어집니다. 각 선수의 키와 몸무게는 모두 다릅니다.


[출력]

첫째 줄에 씨름 선수로 뽑히는 최대 인원을 출력하세요.

[입력예제]

5
172 67
183 65
180 70
170 72
181 60

[출력예제]

3

[출력설명]

(183, 65), (180, 70), (170, 72) 가 선발됩니다. (181, 60)은 (183, 65)보다 키와 몸무게 모두 낮기 때문에 탈락이고, (172, 67)은 (180, 70) 때문에 탈락입니다.

---

[문제풀이과정]

누군가 나보다 키도 크고 몸무게도 많이 나가면 그때 탈락하는것!!
그럼 1번은 3번 때문에 탈락하고
2번은 합격 (키 제일 큼)
3번은 합격
4번은 합격 (몸무게 제일 많이 나감)
5번은 2번 때문에 탈락이다.

그럼 일단 씨름 선수 명수를 변수로 두고 일단 N명을 넣어논 다음, 탈락할 때마다 하나씩 --한다.
반복문 돌면서 한명 한명 기준으로 잡는다.
기준인 사람의 키로 먼저 비교한다.
내 키가 다른 사람들의 키보다 크면 그 사람과는 비교하지 않고 다음 사람으로 넘어간다.
만약 내 키가 다른 사람들의 키보다 작으면 몸무게도 비교한다.
내가 그 사람보다 키는 작지만 몸무게는 크면 그냥 그 사람 통과
만약 몸무게도 작으면 씨름 선수에서 제외되므로 씨름 선수 명수를 --한다.

1. 맨 첫줄 인원 수 N 받아들이기
2. 2차원 배열 [N][2] 만들고 그 아래 적히는거 다 넣기
3. 씨름 명수 변수 만들고 그 인원수 N 넣기
4. 사람 수 N 만큼 반복문 돌리기
5. 그 반복문 안에서 지금 사람을 기준으로 잡기
6. 다시 사람 수 N만큼 반복문 돌려서 지금 사람의 키부터 다른 사람과 비교
7. 만약 키가 크면 비교 않고 다음 사람으로 넘어가기
8. 만약 키가 작으면 몸무게도 비교. 몸무게가 크면 다음 사람으로 넘어가기
9. 만약 키도 작고 몸무게도 작으면 씨름 명수에서 하나씩 빼기
10. 그렇게 모든반복문을 돌린뒤 씨름 명수를 출력하면 그게 답!

여기까지 18분 걸림

문제풀이 30분 걸림

[처음으로 패스한 코드]

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
	    int N = sc.nextInt();
	    int[][] ath = new int[N][2];
	    
	    for(int i = 0 ; i < N ; i++) {
	    	ath[i][0] = sc.nextInt();
	    	ath[i][1] = sc.nextInt();
	    }
	    
	    int athNum = N;
	    
	    for(int i = 0 ; i < N ; i++) {
	    	// i는 기준으로 할 사람의 인덱스임
	    	
	    	for(int j = 0 ; j < N ; j++) {
	    		// j는 비교할 사람의 인덱스임
	    		
	    		if(ath[i][0] < ath[j][0]) {
	    			// 내가 키가 작다면?
	    			
	    			if(ath[i][1] < ath[j][1]) {
	    				// 키도 작고 몸무게도 작으면 나 탈락(비교 끝)
	    				athNum--;
	    				break;
	    			} else {
	    				// 키는 작은데 몸무게는 크면 합격
	    				continue;
	    			}
	    		} else {
	    			// 내가 키 크면 그냥 넘어감
	    			continue;
	    		}
	    	}
	    }
	    
	    System.out.println(athNum);
		
	  }
}

 

통과를 하긴 했는데
이중 for문으로 하면 time limit에 걸린다고 한다!!

왜냐면 N은 아주 크면 30000까지 가능하기 때문. 그래서 다른 방법으로도 풀어봄

---

키를 기준으로 정렬했음
그럼 몸무게만 기준으로 비교하면 됨. 그럼 for문 한번만 쓰면됨
한가지 기준으로 정렬하고 나머지를 비교하며 선택하는 것도
완벽하지 않지만 포괄적인 범위의 그리디 알고리즘이라고 부를 수 있음!!
183 65
181 60
180 70
172 67
170 72
이렇게 정렬하면 맨 첫번째 사람은 키가 제일 크므로 당연히 선수로 합격
일단 몸무게 최댓값에 1번 사람 몸무게 넣어놓기
2번의 몸무게가 최댓값보다 작으므로 탈락
3번의 몸무게는 최댓값보다 크므로 합격. 그리고 최댓값에 3번의 몸무게를 덮어쓰기
4번의 몸무게는 최댓값보다 작으므로 탈락
5번의 몸무게는 최댓값보다 크므로 합격
그래서 총 3명이 합격했다고 하면 되는 것임.

일단 나도 정답 코드 보기전에 이 방식으로 한번 풀어보겠음!!

 

[두번째로 통과한 풀이(키 기준으로 정렬한 뒤 몸무게만 비교)]

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
	    int N = sc.nextInt();
	    int[][] ath = new int[N][2];
	    
	    for(int i = 0 ; i < N ; i++) {
	    	ath[i][0] = sc.nextInt();
	    	ath[i][1] = sc.nextInt();
	    }
	    
	    int athNum = 0;
	    
	    Arrays.sort(ath, new Comparator<int[]>() {
	    	// 선수들 키 큰 순서대로 나열하기!!
	    	
	    	@Override
	    	public int compare(int[] o1, int[] o2) {
	    		if(o1[0] != o2[0]) {
	    			return o2[0] - o1[0];
	    			// 키 기준 내림차순
	    		} else {
	    			return o2[1] - o1[1];
	    			// 키 같으면 몸무게 기준 내림차순
	    		}
	    	}
		});
	    
	    int maxWeight = ath[0][1];
	    // 몸무게 최댓값에 키 제일 큰 사람 몸무게 넣어놓기
	    athNum++;
	    // 키 제일 큰 사람은 무조건 선수로 발탁되야함
	    
	    for(int i = 1 ; i < N ; i++) {
	    	if(ath[i][1] >= maxWeight) {
	    		maxWeight = ath[i][1];
	    		// 만약 비교대상의 몸무게가 최댓값보다 크면 그걸로 최댓값 바꾸고
	    		athNum++;
	    		// 선수 한명 뽑혔으므로 추가해주기
	    	} else {
	    		continue;
	    		// 만약 몸무게가 최댓값보다 작으면 탈락. 최댓값 안 바뀌고 선수로도 안 뽑힘
	    	}
	    }
	    
	    System.out.println(athNum);
		
	  }
}

 

[선생님의 풀이랑 같은점과 다른점]

나는 2차원 배열로, 선생님은 arraylist로 풀었다. compare로 내림차순 하는건 비슷했다.

 

[후기]

이중 for문 돌리면 몇몇개의 테스트 케이스는 시간 초과될 수 있으므로 먼저 키로 정렬한 뒤 몸무게만 비교하는 방식으로 했다. 이중 for문을 돌리면 시간복잡도가 O[n^2]인데 정렬하고 하나만 비교하면 시간복잡도 O[N]이 되므로 가능하면 정렬하고 하도록 하자!