[백준] 1931번 회의실 배정, Python

‍홍승현·2021년 10월 17일
2

문제

백준 1931번

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

풀이

sort 메소드를 사용해서
모든 회의들을 시작시간을 기준으로 오름차순으로 정렬한 뒤
가장 시작 시간이 빠른 회의를 meeting이라는 변수에 넣어주고,
계속 다음 회의들과 비교해가며 회의가 겹치지 않거나
다음 회의가 더 빨리 끝난다면 meeting에 다음 회의를 넣어준 뒤 cnt += 1,
for문을 돌면서 반복

위의 예제 입력 1을 예로 들어 계속 설명하면

import sys
input = sys.stdin.readline

N= int(input()) #회의 수
timeTable = []  

for i in range(N):
    timeTable.append(list(map(int,input().split())))    
#[[A회의 시작시간, A회의 끝나는 시간],[B회의 시작시간, B회의 끝나는 시간] ... ]
#전체 회의를 위의 형태로 만들어서 사용하려고 함.

timeTable.sort() #회의 시작 시간 기준으로 오름차순 정렬
		 #이때 회의 시작 시간이 같으면 끝나는 시간을 기준으로 오름차순

timeTable은 다음과 같이 정렬된다.
[[0, 6], [1, 4], [2, 13], [3, 5], [3, 8], [5, 7], [5, 9], [6, 10], [8, 11], [8, 12], [12, 14]]




meeting = timeTable[0] 
meetingCnt = 1 	       

시작 시간이 가장 빠른 회의를 meeting으로 설정
첫 회의에 대한 카운트 1, 이후 다음 회의로 넘어갈 때마다 += 1



for i in range(1, N): #두 번째 회의부터 마지막 회의까지, 첫 번째 회의는 meeting
    if meeting[0] < timeTable[i][0]: 

다음 회의 시작 시간은 meeting 시작 시간보다 늦거나 같고
다음 회의 시작 시간이 meeting과 같다면 끝나는 시간은 다음 회의가 더 늦거나 같기 때문에
[0, 6], [1, 4] 처럼 다음 회의 시작 시간이 늦은 경우만 다뤄주면 된다.



for i in range(1, N): 
    if meeting[0] < timeTable[i][0]: 
        if meeting[1] <= timeTable[i][0]:
            meeting = timeTable[i] 
            meetingCnt += 1 
        elif meeting[1] >= timeTable[i][1]: 
            meeting = timeTable[i]

두 번째 if문 : [0, 6], [7, 10] 처럼 meeting의 끝나는 시간이 다음 회의의 시작 시간보다도 빠르면 다음 회의를 meeting에 넣어주고 meetingCnt += 1을 해준다.
elif문 : [0, 6], [1, 4]처럼 meeting 끝나는 시간이 다음 회의 끝나는 시간보다 늦으면 meeting을 다음 회의 값으로 바꾸어준다.
이때 [0, 6][1, 4]대체 되는 것이기 때문에 카운트를 해주지 않는다.



print(meetingCnt)

이렇게 하고 meetingCnt를 출력 해주면 맞을거라고 생각했는데 계속 틀렸다.
이해는 안 되지만 회의 시작 시간과 회의 끝나는 시간이 같은 경우,
예를 들어 [4, 4], [5, 5]이런 값이 들어올 수도 있다.

회의 시작 시간이랑 끝나는 시간이 같은 경우가 어딨음....



elif meeting[0] == meeting[1]:
        meeting = timeTable[i]
        meetingCnt += 1

그래서 예외적으로 meeting이 시작 시간과 끝나는 시간이 같다면 다음 회의를 meeting에 넣어주고 카운트를 해주는 코드를 추가했다.

전체 코드

import sys
input = sys.stdin.readline

N= int(input())
timeTable = []

for i in range(N):
    timeTable.append(list(map(int,input().split())))

timeTable.sort()

meeting = timeTable[0]
meetingCnt = 1

for i in range(1, N):
    if meeting[0] < timeTable[i][0]:
        if meeting[1] <= timeTable[i][0]:
            meeting = timeTable[i]
            meetingCnt += 1
        elif meeting[1] >= timeTable[i][1]:
            meeting = timeTable[i]
    elif meeting[0] == meeting[1]:
        meeting = timeTable[i]
        meetingCnt += 1
        
print(meetingCnt)





회의 시작 시간과 회의 끝나는 시간이 같은 경우가 있어서 기분 나쁜 문제

0개의 댓글