파이썬 알고리즘 143번 | [백준 1931번] 회의실 배정 - 그리디

143. 회의실 배정

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

1) 어떤 전략(알고리즘)으로 해결?

• 그리디 알고리즘

2) 코딩 설명

<내 풀이>

import sys

n=int(sys.stdin.readline())
arr=[]
for i in range(n):
    s,e=map(int,sys.stdin.readline().split())
    arr.append((s,e)) 
    #0-> 시작 1-> 끝

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

conf=0 #회의의 갯수
i=0
tmp=[-99]

while i < len(arr) and tmp[-1]!=i:

    tmp.append(i)

    for j in range(i+1,n):
        if arr[i][1] <= arr[j][0]:
            #이미 정렬을 해놓았으니깐 가장 ㄱㅊ
            conf+=1
            i=j
            break

print(conf+1)

<내 틀렸던 풀이, 문제점>

(1) 틀린풀이 : 시간초과

import sys

n=int(sys.stdin.readline())
arr=[]
for i in range(n):
    s,e=map(int,sys.stdin.readline().split())
    arr.append((s,e))
    #0-> 시작 1-> 끝
    arr.sort(key = lambda x:x[1]) ## 이 부분 때문에 시간 초과!!

conf=0 #회의의 갯수
i=0
tmp=[-99]
# for i in range(n):
#     print(i)
    #print(arr[i])
while i < len(arr) :
    if(tmp[-1]==i):
        break
    tmp.append(i)

    for j in range(i+1,n):
        if arr[i][1] <= arr[j][0]:
            #이미 정렬을 해놓았으니깐 가장 ㄱㅊ
            #print(arr[i][1], arr[j][0])
            conf+=1
            i=j
            #print(i)
            break

print(conf+1)

• 시간 초과에 걸리고 말았네

내가 정렬 하는 것을 처음에 for i in range 돌 때마다 넣어서 그럼

(2) 틀린풀이 : 8~90%까지 갔다가 마지막에 틀렸습니다 ㅠㅠ

import sys

n=int(sys.stdin.readline())
arr=[]
for i in range(n):
    s,e=map(int,sys.stdin.readline().split())
    arr.append((s,e))
    #0-> 시작 1-> 끝
    
arr.sort(key = lambda x:x[1])

conf=0 #회의의 갯수
i=0
tmp=[-99]
# for i in range(n):
#     print(i)
    #print(arr[i])
while i < len(arr) :
    if(tmp[-1]==i):
        break
    tmp.append(i)

    for j in range(i+1,n):
        if arr[i][1] <= arr[j][0]:
            #이미 정렬을 해놓았으니깐 가장 ㄱㅊ
            #print(arr[i][1], arr[j][0])
            conf+=1
            i=j
            #print(i)
            break

print(conf+1)

• 이유는 끝나는 시간 정렬 하고, 끝나는 시간이 만약 같다면 빨리 시작하는 애가 더 먼저 오도록 했어햐 했는데, 그러지 않았음
• 그래서 arr.sort(key = lambda x:x[1]) 에서 끝나는 시간만 정렬하던 것을 arr.sort(key = lambda x:(x[1],x[0])) 으로 처리해주었다.

<반성 점>

• 시간을 정렬해서 풓어야겠다는 생각은 했지만, 시작 시간을 정렬해야할 지, 종료 시간을 정렬해야할 지에 대한 판단이 확실하지 않았다.

<배운 점>

지난 문제 복습 +
https://mgyo.tistory.com/166?category=879767

• input()대신 sys.stdin.readline()을 사용하는 이유는?
• 단순히 몇줄 입력받는 문제들과는 다르게, 반복문으로 여러줄을 연속적으로 입력받아야 하는(정렬, 이진 탐색, 최단 경로 문제)의 경우 input()으로 데이터를 입력받으면 시간초과로 오답판정을 받는 일이 발생할 수 있다.
  따라서 입력을 최대한 빠르게 받는 방법을 알아야 한다.