[Algorithm] Softeer [21년 재직자 대회 예선] 회의실 예약 (python)

[ Softeer 연습문제 - 회의실 예약 ]

Softeer - 현대자동차그룹 SW인재확보플랫폼

• 문제명 : 회의실 예약[21년 재직자 대회 예선]
• 사용언어 : python

---

  문제

회사에는 N개의 회의실이 있다. 수많은 팀이 모여 토론하고 업무를 처리하기 위해서는 회의실이 필수적이다.
내부망에 아주 간단한 회의실 예약 시스템이 있지만 편의성이 매우 떨어진다. 단순히 예약된 회의의 목록만 표시되기 때문에, 방 별로 비어 있는 시간이 언제인지를 확인하기가 힘든 것이다. 당신은 이를 직접 해결해 보기로 마음 먹었다.
회의실 이용 규칙은 다음과 같다:

- 회의실은 9시부터 18시까지만 사용 가능하다. 모든 회의의 시간은 이 안에 완전히 포함되어야 한다.
- 회의는 정확히 한 회의실을 연속한 일정 시간 동안만 점유한다. 즉 각 회의는 (회의실, 시작 시각, 종료 시각)의 정보로 나타낼 수 있다.
- 회의의 시작과 종료 시각은 시(時, hour) 단위로만 설정 가능하다. 같은 회의실을 사용하는 회의 시간은 서로 겹칠 수 없다. 여기서 겹친다는 것은, 두 회의 모두에 포함되는 시간이 1시간 이상 존재한다는 것을 의미한다. 예를 들어, 10시-12시의 회의와 11시-13시의 회의는 겹치는데, 11시-12시의 시간이 두 회의 모두에 포함되기 때문이다.
- 한 회의가 끝나는 시각에, 같은 회의실에서 다른 회의가 시작하는 것은 허용된다. 이 경우 두 회의가 겹치지 않기 때문이다.
- 길이가 0인 회의, 즉 시작 시각과 종료 시각이 동일한 회의는 예약된 바 없으며, 새롭게 잡을 수도 없다.

이미 예약된 M개의 회의에 대한 정보가 주어지면, 회의실별로 비어 있는 시간대를 정리해 출력하는 프로그램을 작성해 보자. 구체적인 형식은 아래를 참고하시오.

 

 

 

  알고리즘 및 설명

뭔가 코드가 잘 작성되다가 마지막에 뭔가 꼬였다.. 

 

▼ 처음 짠 코드 (정답 X)

import sys
from collections import defaultdict

N, M = map(int, input().split())
room_names = [input().strip() for _ in range(N)]
n_num = 0

meeting = defaultdict(list)
for _ in range(M):
    name, s_time, e_time = input().split()
    meeting[name].append((int(s_time),int(e_time)))


# 회의실 이름 오름차순 출력
for room_name in sorted(room_names):
    print_list = []
    # 예약된 시간 초기화
    reserved_time = set(range(9,19))

    for start, end in meeting[room_name]:
        reserved_time -= set(range(start, end))
        
    if not reserved_time:
        print_list.append("Not available")
    else:
        # 연속된 구간을 찾기.
        first = 1
        for i in range(9,19):
            if i in reserved_time:
                if first == 1:
                    start = i
                    first = 0
                else:
                    if (i+1) not in reserved_time:
                        end = i
                        print_list.append(f"{start:02d}-{end:02d}")
                        first = 1
                        
    print(f"Room {room_name}:")
    for i in range(len(print_list)):
        print(print_list[i])
        
    if n_num != N-1:
        print("-----")
        n_num += 1

 

이 코드에 이것저것 시도해 보다가 자꾸 코드가 산으로 가서 다른 풀이들도 참고해 보았다.

그러다가 시도해 본, 'check' 라는 변수를 사용해서 안 풀리던 구간 해결해 보기!!

 

 

▼ 수정 후 정답 코드 ▼

import sys

# 주어진 회의 시간을 확인하여 예약 가능한 시간대를 출력하는 함수
def check_time(times):
    available = []
    check = 9

    # 회의 시간을 순회하면서 예약 가능한 시간대 확인
    for time in times:
        start, end = time[0], time[1]
        if check < start:
            available.append([check, start])
        check = end

    # 마지막 회의 종료 시간과 18시 사이의 예약 가능한 시간대 추가
    if check != 18:
        available.append([check, 18])

    able_len = len(available)

    # 예약 가능한 시간대 출력
    if able_len == 0:
        print("Not available")
    else:
        print(f"{able_len} available:")
        for start, end in available:
            print(f"{start:02d}-{end:02d}")


# 입력 받기
N, M = map(int, input().split())
meeting = dict()

for _ in range(N):
    room_names = input()
    meeting[room_names] = []

# 회의에 대한 정보를 입력 받아 meeting 딕셔너리에 저장
for _ in range(M):
    name, s_time, e_time = map(str, input().split())
    meeting[name].append([int(s_time),int(e_time)])


# 회의실 이름 오름차순 출력
for name, times in sorted(meeting.items()):
    print(f"Room {name}:")

    # 시작 시간을 기준으로 정렬
    times.sort(key=lambda x : x[0])
    # 예약 가능한 시간대 출력
    check_time(times)

    # 출력 형식에 맞게 구분선 출력
    N -= 1
    if N != 0:
        print("-----")

 

 

  결과

 

 

 

 

※ 새로 알게 된 것들 ※

 

▷ 시간 표현 : {start:02d}-{end:02d}

  : 변수를 정수로 출력하고, 출력 폭을 2자리로 지정. 남는 공간은 0으로 채우라는 의미

 

▷ times.sort(key=lambda x : x[0])

  : 리스트 'times'의 각 원소를 정렬하는데, 각 원소는 튜플 형태이며 첫 번째 요소에 대해 정렬을 수행한다는 의미.

'lambda x: x[0]'는 익명 함수를 생성하는데, 이 함수는 매개변수 'x'를 받아서 x[0]값을 반환한다. 이 익명 함수는 sort 메서드의 'key' 매개변수에 전달되어 각 원소를 정렬할 때 기준이 된다.

위 코드에서의 의미 → 'times' 리스트를 첫 번째 요소를 기준으로 오름차순으로 정렬하는 것.

회의의 시작 시각을 기준으로 정렬되어 있는 상태가 되고, 후에 코드에서 이를 활용하여 연속된 구간을 찾게 된다.