[알고리즘/java] Greedy Algorithm 그리디 알고리즘 / 씨름 선수

이 글은 인프런 [자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 ] 강의를 수강하며 작성한 글입니다.

- https://inf.run/Azjw

자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 - 인프런 | 강의

---

문제 :

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

 

▣ 입력설명 :

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

 

▣ 출력설명 :

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

 

▣ 입력예제 1 :

5

172 67

183 65

180 70

170 72

181 60

 

▣ 출력예제 1 :

3

 

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

 

 

---

 

이 문제를 한 선수를 나머지 선수들과 비교하는 이중for문으로 풀려고 하면 입력이 커서 시간초과가 나기 때문에 다른 방법으로 풀어야 한다.

 

바로 현재 시점에서 최선의 선택을 하는 알고리즘인 그리디 알고리즘을 사용한다.
-> but 현재 시점에서 최선의 선택이 하는 것이 항상 최선의 결과를 불러오진 않음

-> 그런 문제는 다이내믹 프로그래밍으로 풀어볼 수 있다.

 

선발될 선수는 자기 자신보다 키와 몸무게 값이 모두 큰 선수가 없어야 한다.

그러므로 먼저, 선수들을 키를 기준으로 내림차순 정렬시킨다.

 

183 65

181 60

180 70

172 67

170 72

 

-> 첫번째 선수는 선수들 중 키가 가장 크므로, 이 선수보다 키가 큰 선수는 당연히 없기 때문에 선출되어 count++을 해준다. 그리고 이 선수의 몸무게 값을 max에 넣어준다.

 

 

그리고 그 다음 선수를 보면

 

183 65

181 60

180 70

172 67

170 72

 

-> 자신의 앞선 선수는 자신보다 키가 큰 선수를 의미하기 때문에, 현재 max값보다 자신의 몸무게 값이 작다면

(==키와 몸무게값 둘 다 자신보다 큰 선수가 존재함) 이 선수는 선발될 수 없다.

 

 

다음 선수는 

 

183 65

181 60

180 70

172 67

170 72

 

-> 현재 max값인 65보다 자신의 몸무게가 크므로 이 선수보다 키가 큰 선수는 있어도, 키가 크고 몸무게도 큰 선수는 존재하지 않는다. 그러므로 max값을 자신의 몸무게로 변경하고 선발될 선수로 count++ 해 준다.

 

 

나머지 선수들도 동일한 방식으로 검사한다.

 

 

---

 

< 씨름 선수 전체코드 >

import java.util.*;
import java.io.*;

public class Main {

	private static int N;

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());
		int count = 0;
		int maxWeight = Integer.MIN_VALUE;

		ArrayList<Player> players = new ArrayList<>();

		for (int i = 0; i < N; i++) {
			String[] s = br.readLine().split(" ");
			players.add(new Player(Integer.parseInt(s[0]), Integer.parseInt(s[1])));
		}

		Collections.sort(players);

		for (int i = 0; i < N; i++) {
			if (players.get(i).w > maxWeight) {
				maxWeight = players.get(i).w;
				count++;
			}
		}
		
		System.out.println(count);

	}

	static class Player implements Comparable<Player> {
		int h;
		int w;

		Player(int h, int w) {
			this.h = h;
			this.w = w;
		}

		@Override
		public int compareTo(Player p) {
			return p.h - this.h;

		}
	}

}