[백준] 1931번 회의실 배정 - Python

문제 링크: https://www.acmicpc.net/problem/1931

 

이 문제에서 필요한 아이디어는 그리디 알고리즘을 사용하여 최대한 많은 회의를 배정하는 것입니다.

 

핵심 아이디어

1. 종료 시간 기준 설정
   •  회의를 종료 시간을 기준으로 정렬합니다. 이는 가장 빨리 끝나는 회의부터 고려하기 위함입니다.
   •  종료 시간이 같을 경우, 시작 시간을 기준으로 추가 정렬합니다.
2. 겹치지 않는 회의 선택
   •  현재 고려 중인 회의의 시작 시간이 이전에 선택된 회의의 종료 시간보다 크거나 같은 경우에만 해당 회의를 선택합니다.

이 아이디어는 항상 현재 상황에서 최선의 선택을 한다는 그리디 알고리즘의 원칙을 따릅니다.

 

그럼 코드를 확인해 보겠습니다.

import sys
from typing import List, Tuple

input = sys. stdin. readline

N: int = int(input())
data: List[Tuple[int, int]] = [tuple(map(int, input().split())) for _ in range(N)]

X_INDEX, Y_INDEX = 0, 1
data.sort(key = lambda x: (x[Y_INDEX], x[X_INDEX]))

count = 0
max_y = 0
for x, y in data:
    if x >= max_y:
        count += 1
        max_y = y
print(count)

이번에도 타입 힌팅을 사용해 보았습니다. 사용하지 않아도 무관합니다.

 

1. 라이브러리 및 입력 설정

   import sys
   from typing import List, Tuple
   input = sys.stdin.readline

   •  sys 모듈을 임포트 하여 sys.stdin.readline을 사용합니다. 이는 대량의 입력을 빠르게 처리하기 위한 최적화 기법입니다.
   •  typing 모듈에서 List 와 Tuple을 임포트 하여 타입 힌팅을 사용합니다. 이는 코드의 가독성을 높이고 잠재적 오류를 방지하는데 도움이 됩니다.
2. 입력 처리

   N: int = int(input())
   data: List[Tuple[int, int]] = [tuple(map(int, input().split())) for _ in range(N)]

   •  N은 회의의 수를 나타냅니다.
   •  data는 각 회의의 시작 시간과 종료 시간을 튜플로 저장한 리스트 입니다.
   •  map(int, input().strip())을 사용하여 각 줄의 입력을 정수 튜플로 변환합니다.
   •  N개의 정보를 입력받는 과정이므로 시간 복잡도는 O(N)입니다.
3. 상수 정의 및 정렬

   X_INDEX, Y_INDEX = 0, 1
   data.sort(key = lambda x: (x[Y_INDEX], x[X_INDEX]))

   •  X_INDEX와 Y_INDEX는 튜플의 인덱스를 나타내는 상수입니다. 코드의 가독성을 높이기 위해 사용했습니다.
   •  Python 내장 정렬 함수는 Timsort 알고리즘을 사용하며, 이 시간 복잡도는 O(N log N)입니다.
     •  2024.12.09 - [코딩 테스트] - 파이썬 코딩 테스트를 위한 시간 복잡도 이해하기
4. 그리디 알고리즘 구현

   count = 0
   max_y = 0
   for x, y in data:
       if x >= max_y:
           count += 1
           max_y = y

   •  count는 선택된 회의의 수를 저장합니다.
   •  max_y는 현재까지 선택된 회의 중 가장 늦게 끝나는 시간을 저장합니다.
   •  정렬된 data를 순회하면서, 현재 회의 시간(x)이 이전에 선택된 회의의 종료 시간(max_y) 이후라면 해당 회의를 선택합니다.
   •  회의가 선택되면 count를 증가시키고 max_y를 현재 회의의 종료 시간으로 업데이트합니다.
   •  정렬된 리스트를 한 번 순회하는 과정이므로 시간 복잡도는 O(N)입니다.
5. 결과 출력

   print(count)

   •  최종적으로 선택된 회의의 수를 출력합니다.
   •  이 알고리즘의 전체 시간 복잡도는 O(N log N)입니다.

 

 

 

# 이 글의 내용 중 일부는 Perplexity AI의 도움을 받아 정보를 수집하고 정리하였으며, 추가적인 연구와 개인적인 견해를 더하였습니다.