[파이썬 알고리즘 문제풀이 입문] 이분탐색(결정알고리즘) & 그리디 알고리즘 - 회의실 배정(그리디)

*문제 본문은 강의 내용과 관련되어 있어 자세하게 적지 않았습니다.

 

 

 

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 n개의 회의들에 대하여 회의실 사용표를 만들려고 한다. 각 회의에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라. 단, 회의는 한 번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다.

 

 

 

풀이

• 답안 : Python

import sys
input = sys.stdin.readline

N = int(input())
times = list()

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

times.sort(key=lambda x : (x[1], x[0]))

last = 0
count = 0

for s,e in times:
    if s >= last:
        last = e
        count += 1

print(count)

- 문제 풀 때 내가 생각했던 로직과 답안을 비교해봤을 때 거의 동일했다.

- 기준으로 잡을 때 끝나는 시간이 중요했다. 아무리 시작 시간이 빨라도 늦게 끝나는 경우가 있을 수 있기 때문에, 빨리 끝나는 시간을 우선으로 비교해주었다.

- 정렬 sort()를 할 때, 어떤 것을 기준으로 할 지 지정할 수 있다는 것을 알게 되었다. (key=lambda x : 기준)

- 기준 부분에 2개 이상 작성할 수 있다는 것을 알게 되었다. (앞에 있는 것부터 차례로 기준으로 적용됨)

 

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

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

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

    for(i in meetings) {
        if(i[0] >= last) {
            last = i[1]
            count += 1
        }
    }
    
    println(count)
}

- python과 비슷하게 kotlin도 기준을 2개를 지정해서 정렬을 할 수 있었다. (sortedWith(compareBy({it}, {}, ...)) 사용)

- 기준을 1개만 지정할 때에는 : sortedBy{it} 를 사용해준다.

cf,) sorted → Immutable / sort → Mutable

 

 

** 그리디 알고리즘

: 문제를 풀어나가는 단계에 있어서, 이 단계에서 현재 가장 좋은 것은 무엇인지 파악하고, 선택하는 것

: 가장 좋은 것을 어떻게 판별? → 대부분 다 정렬! (정렬을 한 다음에 차례차례 선택해나가면 된다.)