[그리디] 백준 10775번: 공항 / 골드2

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

10775번: 공항

<시간 초과 코드>

import sys
n = int(sys.stdin.readline())
m = int(sys.stdin.readline())

gate = [0]*(n+1)
count = 0
for i in range(m):
    num = int(sys.stdin.readline())
    
    docking = False
    for j in range(num,0,-1):
        if gate[j]==0:
            gate[j]=1
            count +=1
            docking = True
            break
    if not docking:
        break
print(count)

가능한 한 큰 게이트로 도킹하는 방식으로 그리디하게 접근했다.  

그런데 처음 방법으로는 71퍼에서 시간 초과가 발생했다. 그래서 다른 방법을 생각해보다가

도저히 방법이 떠오르질 않아 위의 코드를 개선시켰다.

 

이중으로된 for문 안에서 num부터 하나씩 빼가며 빈 곳을 찾는 방식이었는데

딕셔너리 하나를 더 추가해서 빈 곳을 찾으면 그 값을 저장시켰다. 이렇게 되면

다음부터 동일한 num을 받더라도 num에서부터 빈 곳을 찾는 게 아니고

테이블에 저장된 곳부터 찾아나가기 때문에 훨씬 시간이 절약된다.

import sys
n = int(sys.stdin.readline())
m = int(sys.stdin.readline())

table = {}
for i in range(1,n+1):
    table[i] = i

gate = [0]*(n+1)
count = 0
for i in range(m):
    num = int(sys.stdin.readline())

    docking = False
    for j in range(table[num],0,-1):
        if gate[j]==0:
            gate[j]=1
            table[num]= j-1
            count +=1
            docking = True
            break
    if not docking:
        break
print(count)