섹션 9. Greedy Algorithm 1. 씨름선수

문제

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

입력

• 첫째 줄에 지원자의 수 N(5<=N<=30,000)이 주어집니다.
• 두 번째 줄부터 N명의 흰돌 능력치와 검은돌 능력치 정보가 차례로 주어집니다.
• 각 선수의 흰돌능력치가 모두 다르고, 검은돌 능력치도 모두 다릅니다. 능력치 값은 1,000,000이하의 자연수입니다.

출력

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

입출력 예제

---

풀이방식

이번 문제는 그리디 알고리즘에 대한 문제이다.

그리디 알고리즘이란 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다.

---

설계과정

1. 섹션 6에서 봤던 문제들에 사용한 방식을 통해 ArrayList 배열을 키만 내림차순으로 정렬한다.

2. 그 후 다시 몸무게를 기준으로 오름차순 정렬한다.

3. Body 클래스의 객체와 arr 배열을 각각 매핑해서 몸무게의 최대값을 구한다.

4. 최대값을 구했으면 cnt에 1씩 누적한다.

5. for문을 수행한 후 cnt를 출력한다.

---

풀이과정

1. 각 변수들을 선언한다.

• 키와 몸무게를 갖고 있는 클래스 Body를 가진 ArrayList 배열  arr 을 선언한다.
• 키를 의미하는 변수 height 을 선언한다.
• 몸무게를 의미하는 변수 weight 을 선언한다.

2. 각 선수들의 키와 몸무게를 가지는 클래스 Body를 선언하고, 내림차순으로 정렬한다.

• 섹션 6. 정렬, 이분검색과 결정알고리즘에서 비슷한 문제들을 복습해보자.
• Body의 height 에서 this.height 를 통해 키를 내림차순으로 정렬한다.

3. solution 메소드를 작성한다.

 

4. 몸무게를 오름차순으로 정렬한다.

• Collections.sort() : 오름차순으로 정렬해준다.

5. for문을 통해 Body 객체와 arr 배열을 각각 매핑해서 몸무게의 최대값을 구한다.

• 키는 이미 정렬되어있으므로 몸무게만 비교하면 된다.

6. 최대값 max 를 찾았으면 cnt를 누적한다.

 

7. 누적된 cnt를 출력한다.

 

---

해당 글은 인프런 > 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비(김태원)강의를 참고하여 작성하였습니다.