[CodingTest] 백준 #1931 회의실 배정

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

1931번: 회의실 배정

 

이 문제는 회의실이 한 개이고, 회의들에 대해 최대 몇 개의 회의를 한 회의실에서 진행할 수 있는지 구하는 문제이다.

처음에 문제를 잘못 읽고 회의실이 여러개이고 모든 회의를 진행하려면 필요한 회의실의 최소 갯수를 구하는 문제인 줄 잘못 알았다. 문제를 잘 읽자 ... 

 

이 문제는 생각하기에 따라 매우 간단히 풀릴 수 있는 문제였는데 나는 진행할 수 있는 회의의 "최대 갯수"에 초점을 맞춰 풀었고 오답이 나왔다 ㅠ 

질문 게시판의 반례를 모두 넣어보았는데 잘 나와서 아직도 반례가 무엇일까 미스테리이다.. 

문제에 보면 힌트도 나와있는데 힌트를 무시하고^^ ㅋㅋ 푼 댓가라 생각한다 .. 

그럼 우선 틀린 풀이부터 살펴보자! 혹시 반례를 아는 분은 댓글로 남겨주시면 감사합니다 .. ㅠ 

 

시도 1 - 실패(틀렸습니다)

n = int(input())
arr = []
res = []
for i in range(n):
    arr.append(list(map(int,input().split())))
#회의 소요시간, 회의 시작시간 순으로 정렬
arr = sorted(arr,key = lambda x:(x[1]-x[0],x[0]))
#회의를 진행할 수 있는 시간을 저장할 left 리스트 
left = [[0,2**31-1]]
idx = 0
for item in arr:
	#정렬한 배열에 대해
    if idx == 0:
    #결과 배열 res에 첫번째 원소 추가
        res.append(item)
        #만약 item이 [3,5]라면 [0,3], [5,~]시간에 회의를 진행할 수 있으므로 left를 다음과 같이 바꿈
        left.append([left[0][0],item[0]])
        left.append([item[1],left[0][1]])
        #[0,2**31,1]값 제거
        left.pop(0)
        #인덱스 늘려주기
        idx+=1
    #첫번째 원소가 아니라면    
    else:
        #시작시간은 item의 0번째, 종료시간은 item의 1번째 수
        s = item[0]
        e = item[1]
        idx+=1
        #left배열을 돌면서
        for i in range(len(left)): 
            
			#회의를 진행할 수 있는 시간이 있는지 살펴본다.
            #ex. item이 [3,5]이고 left가 [[1,6],[7,~]]이면, [3,5]는 [1,5]시간 내에 진행할 수 있으므로
            if s>=left[i][0] and e<=left[i][1]:
            #item의 회의를 진행할 수 있다 판단하고 res에 item을 추가한다.
                    res.append(item)
                    #[1,5] 시간 내에 진행할 수 있다면, [1,6]를 제거하고, [1,3],[5,6]을 left에 추가한다.
                    cal = left.pop(i)
                    if cal[0] !=item[0]:
                        left.append([cal[0],item[0]])
                    if item[1]!=cal[1]:
                        left.append([item[1],cal[1]])
                    break;
                    #left를 정렬한다.
                    left.sort()


print(len(res))

 

 

앞에서도 말했듯이 나는 진행할 수 있는 회의의 갯수에 초점을 맞췄기 때문에, 회의 진행시간이 짧은 순으로 먼저 정렬하고, 그 다음으로 회의 시작 시간이 이른 순으로 정렬했다.

 

left 배열에는 진행할 수 있는 시간을 저장했다.

따라서, 정렬한 값을 순회하면서 left 배열에서 회의가 가능한 시간에 해당 회의를 진행할 수 있는지 판단하고, 회의를 진행할 수 있으면, left를 다시 계산하고 정렬하였다.

 

반례를 ㅠㅠ 아직도 모르겠다 ㅠㅠ 도움 주실 분 .. ㅠ

 

아무튼! 오기로 반례를 찾고 싶었지만 못 찾아서 .. 생각을 다시 하였다.

무시했던 힌트를 다시 생각했다. 

회의 소요 시간이 중요한 것이 아니라  단순히 회의가 끝나는 시간이 중요하다는 것을 깨달았다.

따라서 회의가 빨리끝나는 순으로 정렬하고, 그 다음으로 회의 시작 시간이 빠른 순으로 정렬하면 회의 가능 시간 등을 계산하지 않아도 되는 것이었다 ,,,

추가적으로 회의 시작 시간을 기준으로 정렬하면 예를 들어 (0,13}, {1,2} ... 등일 때 첫 회의가 너무 길어 많은 회의를 진행할 수 없으므로 무조건 회의 종료 시간을 기준으로 생각해야 한다. 

 

그래서 두번째 풀이!

 

두번째 시도 - 성공

import sys
n = int(sys.stdin.readline())
arr = []
res = []
for i in range(n):
    arr.append(list(map(int,sys.stdin.readline().split())))
arr = sorted(arr,key = lambda x:(x[1],x[0]))
e = 0
for item in arr:
    if e<=item[0]:
        res.append(item)
        e = item[1]
print(len(res))

 

한 눈에 봐도 코드가 확 짧아진 것을 알 수 있다 .. ㅠㅠ

그리고! 처음에 input()으로 제출을 했더니 시간이 44000대가 나왔다 ..ㅋㅋ 

readline()으로 바꾸니 다행히 시간이 확 줄었다. 

 

그리디 알고리즘은 현재 할 수 있는 최선의 선택을 계속 해나가나는 알고리즘이다. 

어떤 문제를 풀 때 그 문제가 그리디 알고리즘 관련인 것을 한 눈에 캐치할 수 있었으면 좋겠다 ㅠㅠ