[알고리즘/그리디] 백준 BOJ 1931 회의실 배정

13. BOJ 1931 회의실 배정

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

 

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작 시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

예제 입력 1

11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14

예제 출력 1

4

힌트

(1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다.

 

 

---

💡나의 문제 풀이

문제 해결 아이디어

• 처음에는 (끝-시작)의 차이가 적은 회의부터 오름차순으로 정렬 후, 작은 것부터 선택하면 된다. → 이전에 배운 크루스칼 알고리즘의 방식을 생각해봄
  • 하나씩 순회하며, 이미 선택된 시간에 해당한다면 해당 회의는 스킵해야 한다.
    • 이는 flag 리스트를 만들어서 해당 시간이 비어있는지, 아닌지를 체크하면 될 것 같다. 전체를 True로 설정했다가, 선택될 때마다 해당 시간을 False로 변경
  • 그러나, 정렬을 어떻게 해야 하는 것인가?
  → lambda 작성으로 완료
• # 두 수의 차이가 작은 것부터 오름차순 정렬 data2 = sorted(data,key=lambda x:(x[1])-x[0])
• 이후 힌트 부분을 보고, 내 풀이와는 다른 해답이 나옴을 확인했다. 해답은 총 10시간의 회의 시간을 사용할 수 있지만, 내 풀이의 해답은 9시간의 회의시간을 사용할 수 있다는점..
  • 힌트의 4가지의 회의 시간 순서를 보니, sort를 하지 않은 것 같다.
  • 그렇다면 그냥 순서대로 체크해가면서,

---

작성 코드1

import sys

N = int(sys.stdin.readline())

data = []

max = 0 # 마지막 시간
min = 230 # 처음 시간

for i in range(N):
  a, b = map(int, sys.stdin.readline().split())
  if a>max or b>max:
    max = a if a>b else b
  if a<min or b<min:
    min = a if a<b else b
  data.append([a,b])

# 두 수의 차이가 작은 것부터 오름차순 정렬
data2 = sorted(data,key=lambda x:(x[1])-x[0])
# print(data2)

# data의 (min~max)를 기준으로 전체 회의 시간 설정
flag = [1 for _ in range(min,max+1)]

cnt = 0 

# 회의 시간 작은 것부터 선택하여 flag값 변경
for start, end in data2:
  flag2 = 1
  # flag[start~end] 사이에 1이 하나라도 있는 경우 확인
  for i in range(start+1,end+1):
    if flag[i]==0:
      flag2=0
      break
  if flag2==1:
    cnt+=1
    # print(start, ", ", end, " 선택")
  # 포함된 시간이 없는 경우, flag[start~end] 모두 0으로 변경
    for i in range(start+1,end+1):
      flag[i]=0

print(cnt)

 

---

작성코드 2

• 시간 초과 발생
  • 반복문에서 발생하는 것 같다.. 이걸 어떻게 해결 해야 할까

import sys

N = int(sys.stdin.readline())

data = []

for i in range(N):
  a, b = map(int, sys.stdin.readline().split())
  data.append([a,b])

# 선택된 회의 시간 기록
flag = []

cnt = 0 

flag2=1

for start, end in data:
  flag2=1
  for i in range(start,end+1):
    for start2, end2 in flag:
      if i in range(start2,end2+1):
        flag2=0
        break
  if flag2==1:
    flag.append([start,end])
   
        
  
print(len(flag))

 

---

작성 코드 3

• 이번엔 list 배열을 사용해봄. 역시나 런타임 에러

import sys

N = int(sys.stdin.readline())

data = []

max = 0 # 마지막 시간
min = 230 # 처음 시간

for i in range(N):
  a, b = map(int, sys.stdin.readline().split())
  data.append([a,b])

# 선택된 회의 시간 기록
flag = []

cnt = 0 

'''
다음 회의 시간을 읽을 때마다 고려해야할 사항들
1. 이전에 이미 선택된 회의 시간이랑 겹치는가?
2. 겹치는 이전 회의 시간보다 짧은가?
- 짧다면 변경하기
'''
flag2=1
list = [1 for i in range(231)]

for start, end in data:
  flag2=1
  # print(start,"와 ", end)
  # 우선 이전의 flag 리스트의 값과 비교하여
  # start와 end사이의 값들이 포함되어 있는지 확인
  # 포함되어 있다면 (end-start)값이 더 작으면 해당 값 변경하기
  for start2, end2 in flag:
    if start>=start2 and end<=end2:
      flag.append([start,end])
      flag.remove([start2,end2])
      print([start,end], "를 추가하고 ",[start2,end2],"를 제거")
      flag2=0
      continue
    else:
      for i in range(start,end+1):
        if list[i]==0:
          flag2=0
          print(i,"는 list에 있음")
          break
  if flag2==1:
    flag.append([start,end])
    for i in range(start,end+1):
      list[i]=0
    print([start,end], "를 추가")
        
  
print(len(flag))

 

---

작성코드 4

• 답안 코드를 참고해서 겨우겨우 풀었다. 문제에 대한 이해를 잘 해야 할 것 같다.
• 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다.
• 회의의 시작 시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것따라서, 종료 시간을 기준으로 오름차순 정렬 후, 시작 시간을 기준으로 오름차순을 해주어야 한다.

  import sys
  
  N = int(sys.stdin.readline())
  
  data = []
  
  for i in range(N):
    a, b = map(int, sys.stdin.readline().split())
    data.append([a,b])
  
  # 시작 시간을 기준으로 오름차순 정렬, 이후 끝 시간을 기준으로 오름차순 정렬
  data2 = sorted(data,key=lambda x:(x[1], x[0]))
  # print(data2)
  
  cnt = 0 
  e = 0
  for start,end in data2:
    if start>=e:
      cnt+=1
      e = end
      # print([start,end], " 추가")
  
  print(cnt)
  

• ** [시작 시간≤종료 시간] 이 전제기 때문이다.
• → 오름차순 정렬 시, (1,2), (2,2) 와 같은 회의 시간이 주어졌을 때, 출력은 1이 아닌 2라고 할 수 있다.

 

 

---

답안 코드

• 입력 받으면서 한꺼번에 sorted들 완성하였다. 코드는 짧지만 실행 시간에 큰 영향을 끼치는 것은 아닌 것 같다!

[백준알고리즘] 1931번: 회의실배정 -Python

n = int(input())
time = sorted([tuple(map(int, input().split())) for _ in range(n)], key=lambda x:(x[1], x[0]))
ans = end = 0
for s, e in time:
    if s >= end:
        ans += 1
        end = e
print(ans)

 

---

리뷰 및 점검

• sorted() 함수에 lambda식을 이용해 정렬의 기준을 만들 수 있음을 알게 되었다.
• 문제를 풀 때, 무작정 코드로 구현하기보다는, 문제에 대한 깊은 이해와 분석을 한 뒤 아이디어를 떠올리도록 해보자.
• 정말정말 어려웠던 문제이다.