[백준] 1931번 회의실 배정 - (Python)

https://www.acmicpc.net/problem/1931

1931번: 회의실 배정

문제를 보고 최대, 최소를 물어보는 점을 파악하여 그리디 알고리즘을 이용해야 겠다고 생각했다. 보통 그리디 알고리즘같은 경우 정렬을 통해 해당상황에서의 최선의 경우를 택함으로 해당 문제도 그렇게 접근하려고 했다.

회의를 최대한 많이 하기 위해서는 끝나는 시간을 우선적으로 고려해야 하는데, 그러한 이유로는 시작 시간으로 정렬하여 문제에 접근하면, 끝나는 시간이 제각각이라, (1, 10), (2, 4), (5, 6) 같은 경우 회의를 1번밖에 못하는 결과가 초례된다. 따라서 끝나는 시간을 우선적으로 고려해야한다.

 

※ 고려사항

1. 회의시간 정렬 기준 찾기

2. 최대횟수 카운팅 방법

---

 

1. 회의시간 정렬 기준 찾기

앞서 언급했듯이, 끝나는 시간을 우선적으로 고려해야한다. 단, 동일한 시간의 경우와 끝나는 시간이 같은 회의는 추가적인 정렬이 필요된다. (처음 문제를 접근했을 때, 고려하지 못해서 틀렸음)

예를 들어, (2, 2), (1, 2) 회의시간의 경우 (1, 2), (2, 2) 로 2번 회의할 수 있지만, 끝나는 시간으로만 정렬했을 경우, 해당 회의가 1번으로 측정된다. 따라서 끝나는 시간으로 정렬 후, 같은경우에 대해서는 시작시간 정렬을 해줘야 한다.

list의 정렬은 sort와 sorted가 있는데, 간단하게 차이를 비교해보자.

 

sort는 원본값 자체를 수정하지만, sorted는 원본과 수정본을 각각 따로 처리한다.

 

sort vs sorted 예시

a = [1, 3, 2]
sort_a = a.sort()
sorted_a = sorted(a)

print(sort_a, sorted_a)

# 원본 배열 수정
a.sort()
print(a)

# -------------출력----------------
None [1, 2, 3]
[1, 2, 3]

 

그렇다면, 입출력을 어떻게 받으면 좋을까?

회의 시작시간과, 끝나는 시간을 하나의 리스트 또는 튜플로 받아, 이것을 회의시간 리스트에 저장하는 것이 좋다고 생각되었다. 이유는 그렇게 해야 sort 메소드를 통해서 각각의 요소에 접근하여 정렬이 용이하기 때문이다.

 

회의시간 입출력

import sys
input = sys.stdin.readline

# 회의목록
meet = []

n = int(input())

# 회의시간 입력받음
for i in range(n):
    meet.append(list(map(int, input().split())))

 

2차원 배열로 받았기 때문에 끝나는 시간으로 정렬 후, 동일한 경우 시작시간으로 정렬을 해주어야 한다. 따라서 key값으로 lamda식을이용하면 손쉽게 정렬할 수 있다. 

그렇다면 lamda식에 대해 간략하게 짚고 넘어가보자.

lamda식의 경우 1회성으로 함수를 사용하는 경우, 코드의 가독성과 메모리 절약을 위해 자주 사용되는 함수이다. 다음 예제를 확인해보자.

 

function vs lamda 예시

# 일반적 함수 -> 할당
def mul_func(x, y):
    return x * y

print(mul_func(10, 50))             # 500


# 람다 함수 -> 할당
lambda_mul_func = lambda x, y: x * y
print(lambda_mul_func(50,50))       # 2500

 

해당 문제에서는 정렬을 회의시간을 기준으로 1번만 사용하기 때문에 함수를 생성하는것 보다, lamda를 이용하는 것이 용이하다. sort함수의 경우 key를 이용한 정렬이 가능하기 때문에 이곳에 lamda식을 구현한다.

 

회의시간 정렬

# 끝나는 시간순으로 정렬후, 동일경우 시간시간 순으로 정렬
meet.sort(key = lambda x: (x[1], x[0]))

[[1, 4], [3, 5], [0, 6], [5, 7], [3, 8], [5, 9], [6, 10], [8, 11], [8, 12], [2, 13], [12, 14]]

lambda x: (x[1], x[0]) 경우 끝나는 시간으로 정렬후, 해당 시간이 동일하다면, 시작시간이 더 빠른 회의를 우선적으로 정렬한다는 뜻이다. 해당 내용이 이해가 잘 되지 않는다면, lamda 함수와 sort 메소드의 key 부분에 대해서 추가적인 학습을 하면 좋다고 생각됩니다.

 

2. 최대횟수 카운팅 방법

이제 정렬을 했으므로, 카운팅 방법만 고려하면 된다. 회의시간은 정렬된 첫 원소부터 시작해야한다. 왜냐하면 회의시간이 가장 빨리 끝나기 때문에 많은 회의를 할 수 있기 때문이다. 그리고 첫 회의의 끝나는 시간보다 같거나 큰 회의 시작시간으로 이동하면 된다. 그렇게 되면 자동적으로 최대 회의를 할 수 있게 구현할 수 있다.

 

while 처리

end = meet[0][1]
i = 1
cnt = 1

while True:
    if i == n:
        break
    if end <= meet[i][0]:
        end = meet[i][1]
        cnt+=1
    i+=1
print(cnt)

처음 시도했을 때는 while구문으로 코드를 작성했으나, for문을 통해서 접근하는 것이 더 적합하다고 생각되어 코드를 수정했다.

 

for 처리

# 끝나는 시간
end = meet[0][1]

# 회의 횟수
cnt = 1

# 회의끝나는 시간보다 같거나 큰 부분만 고려
for i in range(1, n):
    if end <= meet[i][0]:
        end = meet[i][1]
        cnt+=1

print(cnt)

 

 

 

---

전체코드

import sys
input = sys.stdin.readline

# 회의목록
meet = []

n = int(input())

# 회의시간 입력받음
for i in range(n):
    meet.append(list(map(int, input().split())))

# 끝나는 시간순으로 정렬후, 동일경우 시간시간 순으로 정렬
meet.sort(key = lambda x: (x[1], x[0]))

# 끝나는 시간
end = meet[0][1]

# 회의 횟수
cnt = 1

# 회의끝나는 시간보다 같거나 큰 부분만 고려
for i in range(1, n):
    if end <= meet[i][0]:
        end = meet[i][1]
        cnt+=1

print(cnt)

---

그리디 알고리즘을 오랜만에 풀어보았습니다. 현재까지 그리디 알고리즘을 접근할 때, 그리디인지 여부, 그리고 정렬처리로 구현할 수 있는지 등을 확인하면서 문제에 접근하고 있습니다. 해당문제도 그렇게 접근했었지만, 정렬처리를 2번하는 부분을 떠올리지 못하여, 1번만에 성공하지 못했습니다. 그 덕분에, 정렬과 lamda에 대해서 다시 복습할 수 있는 좋은 문제였던 것 같습니다. 정답률에 비해서는 다소 평이다고 생각됩니다.

설명의 오류나, 궁금하신점은 언제든 피드백 해주시면 감사하겠습니다 ^~^