[파이썬 알고리즘 문제풀이 입문] 이분탐색(결정알고리즘) & 그리디 알고리즘 - 씨름 선수(그리디)

 

 

 

 

문제

현수는 씨름 감독입니다. 현수는 씨름 선수를 선발공고를 냈고, N명의 지원자가 지원을 했습니다. 현수는 각 지원자의 키와 몸무게 정보를 알고 있습니다. 현수는 씨름 선수 선발 원칙을 다음과 같이 정했습니다.
"다른 모든 지원자와 일대일 비교하여 키와 몸무게 중 적어도 하나는 크거나, 무거운 지원자만 뽑기로 했습니다."
만약 A라는 지원자보다 키도 크고 몸무게도 무거운 지원자가 존재한다면 A지원자는 탈락입니다.

 

 

 

풀이

• 답안 : Python

import sys
input = sys.stdin.readline

N = int(input())
info = list()

for i in range(N):
    a, b = map(int, input().split())
    info.append((a, b))

info.sort(reverse=True)

largest = 0
count = 0

for cm, kg in info:    
    if kg > largest:
        largest = kg
        count += 1
    
print(count)

- 키가 제일 큰 순서대로 정렬을 하고 나면 → 키와 몸무게 둘 다 볼 필요없이, 몸무게만 가지고 답을 구할 수 있다는 것을 알게 되었다.

- 그 이외의 것들은 이전 문제와 동일하다고 생각된다.

 

• 답안 : Kotlin (내가 바꿔본 것 / 정확X)

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

fun main(args: Array<String>) = with(BufferedReader(InputStreamReader(System.`in`))){
    var N = readLine().toInt()
    var info : MutableList<List<Int>> = mutableListOf()
    for(i in 0 until N) {
        val (a, b) = readLine().split(" ").map { it.toInt() }
        info.add(listOf(a, b))
    }
    
    info.sortByDescending {it[0]}
    var largest = 0
    var count = 0

    for(i in info) {
        if(i[1] >= largest) {
            largest = i[1]
            count += 1
        }
    }
    
    println(count)
}

- 키를 기준으로 역순으로 정렬 : sortByDecending { } 사용