[백준 19598번] 최소 회의실 개수 - Python

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

19598번: 최소 회의실 개수

풀이

사용한 알고리즘 : 라인 스위핑

 

풀이전략

1. 시작점과 끝점에 대한 튜플 배열을 별개로 생성한다.

    시작점의 튜플은 (시작점 위치, 1) 끝점의 튜플은 (끝점 위치, -1)로 만든다.

    위 문제에서 주어진 예제 입력 1번을 예로들면 아래와 같다.

 

     시작점 배열 = [ [0,1], [15,1], [5,1] ]

     끝점 배열 = [ [40,-1], [30,-1], [10,-1] ]

 

2. 시작점 배열과 끝점 배열을 합치고 튜플의 첫 번째 값을 기준으로 오름차순 정렬한다.

     graph = [ [0,1], [5,1], [10,-1], [15,1], [30,-1], [40,-1] ]

 

3. 특정 위치에서 현재 방 개수를 나타내는 변수와 방이 가장 클 때를 저장하는 변수를 각자 0으로 정의한다.

     roomCount=0  ,  maxCount=0

 

4. graph 모든 튜플 원소들을 순회하면서 튜플의 두번째 값이 1이면 현재 방 개수를 1더하고,

   두번째 값이 -1이면 현재 방 개수에서 1을 뺀다.

 

5. graph 순회 중, 튜플 원소의 첫 번째 값이 변경되면 현재 방 개수와 maxCount를 비교하여

   만약 현재 방 개수가 더 크면 maxCount를 현재 방 개수로 변경한다.

 

6. 맨 마지막 위치에서 현재 방 개수와 maxCount 비교가 반복문 내에서 실행되지 않으므로

    한 번 더 비교하여 maxCount의 개수를 구한다.

 

7. maxCount의 개수를 출력한다.

 

 

제출 코드

import sys

input = sys.stdin.readline

N=int(input())
graph=[]

for i in range(N):
    a,b=map(int,input().split())
    graph.append((a,1))
    graph.append((b,-1))

graph.sort()
roomCount=0
maxCount=0
temp=graph[0][0]

for i in graph:
    if temp!=i[0]:
        if roomCount>maxCount:
            maxCount=roomCount
        temp=i[0]
    if i[1]==1:
        roomCount+=1
    else:
        roomCount-=1

if roomCount>maxCount:
    maxCount=roomCount

print(maxCount)