[백준 1931번] 파이썬 - 회의실 배정

문제 참고 https://www.acmicpc.net/problem/1931

1931번: 회의실 배정

 

 

정해진 시간 동안 가장 많이 회의를 진행하는 문제였다.

시작 시간과 끝나는 시간에 대한 정렬을 통하여 비교 기준을 저장해주고 반복문을 통해 비교를 해주었다.

 

처음엔 정렬을 하지않고 2중 for문을 통하여 기준을 그때그때 바꿔주려고 하였다.

# 1931_회의실 배정

# N개의 회의에 대해 회의실 사용표를 만든다.
# 각 회의 I에 대해 시작 시간과 끝나는 시간이 있고 회의가 겹치지 않으며 사용할 수 있는 최대 개수
# 회의는 중간에 중단 불가하고 회의의 시작 시간과 끝나는 시간이 같을 수 있다.

# 전체 회의 수
T = int(input())
meet = [list(map(int, sys.stdin.readline().split())) for _ in range(T)]

# 회의시간 끝나는 시간 기준으로 정렬
# 시작시간으로 브루트포스를 이용하여야 되서 시간초과가 난다.
meet.sort(key= lambda x: x[1])

# 겹치는 시간에서 회의 시간이 짧을 수록 더 많은 회의가 진행될 수 있다.
# 회의시간이 짧은 애부터 돌아가며 길이를 저장 후 비교한다.
# 전체 회의 수 저장
max_cnt = 0

# 1. 시간초과
for i in range(len(meet)):
    # 끝나는 회의 저장 해두고 비교 기준으로 사용
    end_meet = meet[i]
    # 회의 개수 초기값 1로 저장
    cnt = 1
    if end_meet[1] <= meet[i][0]:
        break

    for k in range(i+1, len(meet)):
        # 회의 끝나는 시간과 시작하는 시간이 같거나 크다면
        if end_meet[1] == meet[k][0] or end_meet[1] < meet[k][0]:
            cnt += 1
            # 끝나는 회의 바꿔주기
            end_meet = meet[k]

        # 회의 개수가 이전 값보다 크다면 새로 저장
        if cnt > max_cnt:
            max_cnt = cnt

print(max_cnt)

테스트 케이스를 돌릴 때는 원하는 값이 잘 나왔지만, 여러 엣지 케이스를 겪기전에 '시간 초과'라는 문제를 맞이했다..

 

시간 초과가 걸릴 때는 전부 지우고 새로 코드를 짜보는 것이 제일 좋은 것 같다.

'정렬'을 이용하는 것이 가장 효과 적일 것이라고 생각하였고 아래와 같이 코드를 구성하였다.

 

import sys
sys.stdin = open ('input.txt')

# 1931_회의실 배정

# N개의 회의에 대해 회의실 사용표를 만든다.
# 각 회의 I에 대해 시작 시간과 끝나는 시간이 있고 회의가 겹치지 않으며 사용할 수 있는 최대 개수
# 회의는 중간에 중단 불가하고 회의의 시작 시간과 끝나는 시간이 같을 수 있다.

# 전체 회의 수
T = int(input())
meet = [list(map(int, sys.stdin.readline().split())) for _ in range(T)]

# 회의시간 끝나는 시간 기준으로 정렬
# 시작시간으로 브루트포스를 이용하여야 되서 시간초과가 난다.
# 회의 시작시간 = 끝나는 시간인 회의가 있을 수 있으므로 시작시간 오름차순 후 끝나는 시간 오름 차순 정렬해줘야 함
meet.sort(key= lambda x: x[0])
meet.sort(key= lambda x: x[1])

# 회의수 저장, 첫 회의가 포함되어 있기 때문에 1
cnt = 1
# 기준이 되는 회의 종료 시간 저장
end_meet = meet[0]
# 다음 회의부터 시작해서 비교한다.
for i in range(1, len(meet)):
    if meet[i][0] >= end_meet[1]:
        cnt+=1
        end_meet = meet[i]

print(cnt)

• 람다 함수를 이용하여 key로 사용해주었고, 시작하는 시간을 기준으로 정렬한 후에, 끝나는 시간에 대해 정렬 해주었다.

확실히 그리디 문제를 풀다보니 문제에 대한 접근 방법 시야가 넓어지는 것 같다고 생각한다. 아직 여러 알고리즘과 자료구조에 대해 겪어보지 못해서 그럴 수도 있다