코딩 테스트/백준

[Python] 백준 1931 회의실 배정

위시리 2024. 10. 21. 22:13

 

 

문제 분석

  • 한 개의 회의실, 사용하고자 하는 팀 N개
  • 각 회의 I에 대해 시작시간 & 끝나는 시간이 주어짐
  • 각 회의가 겹치지 않고, 회의실을 이용할 수 있는 최대 개수 찾기
  • 회의는 시작하면 중단 x
  • 회의의 시작시간과 끝나는 시간이 같을 수 있다. == 시작하자마자 끝남

 

코드 설계

  • 이용할 수 있는 최대 회의 수 : 끝나는 시간이 빠른 회의부터 넣으면 많은 회의를 할 수 있음
  • 시작시간이 빠른 것부터 정렬하면 언제 끝나는지 모르기 때문에 많이 넣기 힘듦

 

정답 코드

실패..

import sys
input = sys.stdin.readline

n = int(input())
time = [list(map(int, input().split())) for _ in range(n)]
time.sort()

meeting = []
for i in range(len(time)):
    if i == 0 :
        meeting.append(time[i])
        e = time[i][1] # 종료시간
    else : # 회의실을 누가 쓰고 있음 앞서 쓰고 있던 팀이 아직 끝나지 않았다면 다음 회의 순서로 넘어감
        if e > time[i][0] : # 끝나는 시간보다 시작시간이 이후이면
            continue
        else :
            meeting.append(time[i])
            e = time[i][0]

print(len(meeting))

실행시간이 더 짧은 경우를 고려하지 않음

 

다른 사람 코드 1

import sys
input = sys.stdin.readline

n = int(input())
meetings = []

for _ in range(n):
    start, end = map(int, input().split(" ")) 
    meetings.append((start, end))

meetings.sort(key=lambda x : (x[1], x[0]))

time = 0
cnt = 0

for start_meeting, end_meeting in meetings:
    if time <= start_meeting :
        time = end_meeting
        cnt += 1 

print(cnt)
  • meeting.sort(key=lambda x : (x[1], x[0]))
  • 종료시간을 우선으로 정렬하고, 종료시간이 같은 경우 시작시간을 기준으로 정렬

 

for _ in range(n): # 대기 회의 개수만큼 반복
    start, end = map(int, input().split(" ")) # 띄어쓰기를 기준으로 입력
    meetings.append((start, end))
    
# print(meetings)
# [(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9), (6, 10), (8, 11), (8, 12), (2, 13), (12, 14)]
# 종료시간 오름차순 정렬, 시작 시간 오름차순 정렬
meetings.sort(key=lambda x : (x[1], x[0]))

# print(meetings)
# [(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9), (6, 10), (8, 11), (8, 12), (2, 13), (12, 14)]

끝나는 시간을 기준으로 정렬해야 최대한 빨리 끝내고 다음 회의를 진행시킴으로 더 많은 회의를 진행할 수 있다.

time = 0 # 끝나는 시간
cnt = 0

for start_meeting, end_meeting in meetings:
    if time <= start_meeting : # 끝나고 다서 다음 회의가 시작할 수 있다면
        time = end_meeting # 끝나는 시간 갱신
        cnt += 1 # 들어간 회의 추가

print(cnt)

 

2회차 - 2024.10.21

import sys
input = lambda : sys.stdin.readline()

n = int(input())
meeting = []

# 입력
for _ in range(n) :
    start, end = map(int, input().split())
    meeting.append((start, end))

# 정렬
meeting.sort(key=lambda x : (x[1],x[0]))

# 갯수 세기
cur_end = 0
cnt = 0
for start, end in meeting :
    if cur_end <= start :
        cur_end = end
        cnt += 1

print(cnt)

 

3회차 - 2025.02.06

현재는 골드 5

pseudo code

회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자

  1. 최대 개수를 어떻게 구할 수 있을까?
    1. 시작 시간을 기준으로 정렬하면 언제 끝나는지 확인을 다 해줘야 한다.
      / 회의 시간이 길어진다면 다른 회의를 선택하지 못하는 경우 발생
    2. 회의 시간이 짧은 순서대로 정렬한다면,
      시작/끝 시간을 알지 못한다. 정렬을 했을 때도 다음에 시작하는 적절한 회의를 찾기 힘들다.
    3. 따라서 종료시간을 기준으로 정렬해서 일찍 끝나는 것들부터 한다면, 남는 시간이 길어져 더 많은 수의 회의를 진행할 수 있을 것이다.
  2. pseudo code
    1. 종료시간을 기준으로 정렬
    2. 종료 시간을 확인하고, ( 종료 시간 <= 시작시간 ) 인 list를 찾아서 체크
    3. 체크된 회의의 수 만큼 count

 

  • 찾기 용이하도록 정렬 : 다차원 배열일 때 특정 차원에 대해서 정렬하는 방법 by lamdba
    • 종료시간을 기준으로 정렬 → 종료시간이 같을 경우, 시작 시간으로 정렬
# 2차원 배열에서 1차원을 기준으로 정렬
meeting = sorted(meeting, key=lambda x : (x[0], x[1]))

# 2차원 배열에서 2차원을 기준으로 정렬
meeting.sorted(key = lamdba x : (x[1], x[0]))

 

정답 코드

import sys
input = sys.stdin.readline

n = int(input())
meeting = [list(map(int, input().split())) for _ in range(n)]
meeting = sorted(meeting, key=lambda x : (x[1], x[0]))
ans = 0

# 다음 순서로 진행할 회의 찾기
cur_start, cur_end = 0, 0
for start, end in meeting :
    if cur_end <= start :
        cur_start = start
        cur_end = end
        ans += 1

print(ans)

 

시간 복잡도 (by chatGPT)

🔍 코드의 시간 복잡도 분석

주어진 코드는 회의실 배정 문제를 해결하는 그리디 알고리즘입니다.
이제 코드의 각 부분별로 시간 복잡도를 분석해 보겠습니다.

📌 코드 구조별 시간 복잡도 분석

1️⃣ 입력 처리

n = int(input())  
meeting = [list(map(int, input().split())) for _ in range(n)]
  • input() 호출: O(1)
  • list(map(int, input().split()))는 한 줄을 읽어 int로 변환하므로 O(1)
  • 위 과정이 n번 반복되므로 전체 시간 복잡도: O(n)

2️⃣ 정렬

meeting = sorted(meeting, key=lambda x : (x[1], x[0]))
  • 정렬 시간 복잡도: sorted()는 **Timsort (O(n log n))**을 사용
  • 따라서 이 부분의 시간 복잡도: O(n log n)

3️⃣ 그리디 탐색

cur_start, cur_end = 0, 0
for start, end in meeting :
    if cur_end <= start :
        cur_start = start
        cur_end = end
        ans += 1
  • for start, end in meeting: O(n)
  • if cur_end <= start: O(1) (단순 비교)
  • 따라서 전체 루프의 시간 복잡도: O(n)

⏳ 전체 시간 복잡도

각 단계별 시간 복잡도를 정리하면:

  1. 입력 처리: O(n)
  2. 정렬: O(n log n)
  3. 탐색(그리디 선택): O(n)

👉 전체 시간 복잡도는 O(n log n) 🎯

🚀 최적화 여부 검토

  • 정렬이 가장 큰 영향을 미치는 단계 (O(n log n)).
  • **탐색 부분(O(n))**은 불필요한 연산 없이 최적화되어 있음.
  • 즉, 이 코드의 시간 복잡도는 최적이며 더 최적화할 필요 없음. ✅

 

저작자표시