친구랑 누가 누가 빨리 푸나 내기하면서 풀었던 소프티어 문제다. 난도는 별 두 개, 정답률은 64%이다.
문제보기
문제를 간단히 설명하자면, n개의 회의실이 있고, 이용가능시간은 9-18시. 시간 단위로 회의실을 사용할 수 있다. m개의 회의 정보가 주어질 때, 이용 가능한 회의시간을 출력하는 문제다.
예제
입력 예제
3 7
grandeur
avante
sonata
sonata 14 16
grandeur 11 12
avante 15 18
sonata 10 11
avante 9 12
grandeur 16 18
avante 12 15
출력예제
Room avante:
Not available
Room grandeur:
2 available:
09-11
12-16
Room sonata:
3 available:
09-10
11-14
16-18
아이디어 구상
회의실 배정 문제를 백준에서 풀어봤었다. 그때에는 최적해를 구하는 거였어서 그리디로 풀었던 것 같은데, 이 문제는 n,m 값이 각각 50개, 100개 제한이므로 그냥 구현을 하면 되겠다고 생각했다.
전체적인 구조는 처음 입력을 dict자료형으로 받아서 각 미팅룸에 해당하는 시간들을 value로 몰아두고, 각 미팅룸별로 이용가능한 시간을 계산하는 함수를 돌려서 처리하도록 했다. 원래는 dict에 넣은 value들이 2차원 배열이 되니까 lambda함수로 앞자리를 기준으로 리스트를 정렬하여 시간 순서대로 삭제해주려고 했는데 이렇게 하니깐 배열이 None으로 되어서 순서는 고려하지 않았다.
여기서 포인트는 이용가능한 시간을 어떻게 추려낼 것이냐였다. 사용은 1시간 단위로 이뤄지기 때문에 구간별로 배열에 넣어 계산해도 되고, 시간으로 넣어 계산해도 되지만 나는 시간단위로 했다. (배열에 9~18을 정수 단위로 넣고 이미 사용이 불가한 시간을 제거했다.)
문제는 9-11시가 가능할 때, 09-11, 10-11이 모두 출력되었는데 이를 끝 두자리가 겹치면 뒷 시간대는 넣지 않도록 하여 해결하였다. 이 이용가능한 시간을 추려내는 방법을 더 최적화 하면 좋을 듯 하다.
사용한 방법들
- dictionary를 Sort할 때에는 sorted함수를 사용해야하고,(sort는 없다)
- sorted(meetings.items())해야 키와 value가 하나의 쌍으로 묶이며 회의실 이름의 알파벳 순으로 정렬이된다. 그리고 이 값은 리스트로 바뀌어 반환된다.
구현
n , m = map(int, input().split())
meetingrooms = []
meetings = {}
for i in range(n) :
room = input()
meetingrooms.append(room)
meetings[room] = []
meetingrooms.sort()
for j in range(m) :
name, start, end = input().split()
start = int(start)
end = int(end)
for k in range(n) :
if name == meetingrooms[k] :
meetings[name].append([start, end])
def calcAvail(times) :
whole = list(range(9,18))
for s,e in times :
for i in range(s,e) :
whole.remove(i)
if len(whole) == 0 :
return 'Not'
else :
start = 0
end = 0
avail = []
for h in range(len(whole)) :
start = whole[h]
end = whole[h]+1
while (end in whole):
end +=1
if start != end :
if len(avail)!=0 :
if str(end) != avail[-1][-2:]:
avail.append(str(start).zfill(2) + '-' + str(end))
else :
avail.append(str(start).zfill(2) + '-' + str(end))
return avail
for room in meetingrooms :
print('Room', room, ":")
times = meetings.get(room)
answer = calcAvail(times)
if answer == 'Not' :
print('Not available')
else :
print(len(answer), 'available:')
for a in answer :
print(a)
if room != meetingrooms[-1] :
print('-----')
해설
소프티어에서 해설해주는 강의가 있다. 참고해보면 좋을 듯하다.
https://www.youtube.com/watch?v=Dl0iLQtEXDQ&t=988s
해설에서는 room이라는 딕셔너리에 1차원 배열을 value로 받는데, 이 때 value는 18개의 원소를 갖고, 이는 각 시간의 이용가능성을 체크한다. 먼저 이렇게 18개의 원소를 0으로 초기화를 한 뒤, 회의실 정보를 입력을 받는다.
그리고 start시간부터 end시간까지(이용불가한 시간)의 값을 1로 바꿔준다. 예를들어 그랜저회의실은 11시에서 12시, 16-18시에 이용불가한데, 그러면 그랜저라는 키의 value는
[0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1,1]와 같다. 인덱스 11,16,17의 값을 1로 바꾼다.
다음 딕셔너리를 알파벳 순으로 정렬하고, 이제 회의실 별 이용가능시간을 출력하면 된다.
이때 0>1로 1>0으로 바뀌는 부분을 잘 조작하면 답을 얻을 수 있다. current라는 인덱스를 도입해서 현재 1일때 0으로 값이 바뀌면 이용 불가능에서 가능으로 바뀌는 부분이니까 이게 우리가 찾는 답이다. 따라서 1에서 0으로 바뀌는 값을 찾아 시작값인 sTime으로 두고 (current =0으로 바꾼다), 1에서 0으로 바뀌는 값을 찾아 eTime으로 두고 temp라는 새로운 배열에 그 값을 저장해둔다. 이때 .. 0으로 끝나면 current가 1이 되지 않고 끝나므로 이때는 18시까지 이용가능한 것이 된다.
그리고 이 값을 주어진 조건에 맞춰 출력한다.
회고
시간을 담아서 삭제하고 출력하는 것이 잘못된 로직이었나 싶었지만 그런 방식으로 접근하는 것은 맞았다. 하지만 더 간단히 하려면 해설에서와 같이 0,1로 저장하고 값이 바뀌는 부분을 체크하는 식으로 했으면 더 간단했겠다. 가능과 불가능을 배열로 체크할 때 , 0과 1을 사용해보자.
