1931번 회의실 배정

 

 

1) 사이트

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

1931번: 회의실 배정

 

 

2) 문제

회의 시작시간과 종료시간을 보고, 최대한 많이 회의를 할 수 있게 시간표를 짜주면 되는 문제이다.

여기서 잊어선 안되는 부분은 "시작시간과 종료시간이 같으면 시작하자마자 끝난다고 보면 된다."

 

 

3) 파이썬 코드

#1. 최대로 채택할 수 있는 회의의 수
n=int(input())
#2-1. 2-dimention array (시작시간, 종료시간)
time=[[0]*2 for _ in range(n)]

#2-2. 시작시간, 종료시간 n+1개 입력받기
for i in range(n):
  time[i]=list(map(int,input().split()))


#3. 끝나는 시간이 빠른 순으로 sort
time=sorted(time, key=lambda x : x[0])
time=sorted(time, key=lambda y : y[1])

#4. 회의실 배정
result=1 #최대 회의 수

present_end=int(time[0][1])

#4-1. 빨리 끝나는 회의로 시작한다. time[0][0]~[1]
for j in range(1,n):
  #이전 회의의 끝나는 시간보다는 시작시간이 커야함. -> 크다면 인덱스 저장
  if present_end<=int(time[j][0]):
    result+=1
    present_end=int(time[j][1])
    
  elif result>=n:
    break

print(result)

 

3-1) 선수 지식

파이썬 코드를 이해하기 위해 알아야 할 선수 지식이 있습니다.

 

1. 숫자 리스트 정렬하는 방법

아무런 조건 없이 정렬하는 방법

>리스트명.sort() : 0열에 있는 데이터를 기준으로 정렬

 

특정 열 기준으로 정렬하는 방법

>sorted(리스트명, key=lambda x : x[1]) : 1열에 있는 데이터를 기준으로 정렬

 

 

2. split된 자료들 int로 변환하기

>list(map(int,input().split()))

 

 

4) 오답 코드와 이유

#1. 최대로 채택할 수 있는 회의의 수
n=int(input())
#2-1. 2-dimention array (시작시간, 종료시간)
time=[[0]*2 for _ in range(n)]

#2-2. 시작시간, 종료시간 n+1개 입력받기
for i in range(n):
  time[i]=input().split()

#3. 끝나는 시간이 빠른 순으로 sort
inter_start=0
inter_end=0
for i in range(n):
  for j in range(i+1,n):
    #끝나는 시간이 나보다 빠른게 있으면 자리 교체
    if int(time[i][1])>int(time[j][1]):

      inter_start=int(time[i][0])
      inter_end=int(time[i][1])

      time[i][0]=int(time[j][0])
      time[i][1]=int(time[j][1])

      time[i+j][0]=inter_start
      time[i+j][1]=inter_end

#4. 회의실 배정
result=1 #최대 회의 수

present_end=int(time[0][1])
restart=1 #탐색위치

#4-1. 빨리 끝나는 회의로 시작한다. time[0][0]~[1]
for j in range(restart,n):
  #이전 회의의 끝나는 시간보다는 시작시간이 커야함. -> 크다면 인덱스 저장
  if present_end<=int(time[j][0]) and result<=n:
    result+=1
    present_end=int(time[j][1])
    restart=j+1
    
  elif restart>=n:
    break

print(result)

1)O(N^2)가 소요되는 거품정렬을 써서 시간이 많이 들어갔다. sort 쓰는 법을 모르기도 해서 이번에 제대로 배웠다.

2)또한 시작시간으로 정렬 1번해주고, 종료시간으로 정렬 1번해주는 과정을 해야하는데, 시작시간으로 정렬하는 과정을 생략했다.

 

 

---

END