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)
회의 시작 시간과 회의 끝나는 시간이 같은 경우가 있어서 기분 나쁜 문제