[백준 10775번] 공항(파이썬)

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

10775번: 공항

이 문제는 풀이방법은 단순할 수 있지만

어떻게하면 반복문을 줄일 수 있는가에 대해서

생각해보면 좋은 문제입니다.

 

우선, 아래는 제가 처음 이 문제를 보자마자

바로 떠올린 코드입니다.

#백준 10775번 공항

G=int(input())
P=int(input())
gate=[i for i in range(1,G+1)]
g_in=[False]*(G+1)
planes=[]
for _ in range(P):
    g=int(input())
    planes.append(g)

answer=0
for gi in planes:
    go=False
    for ga in range(gi,0,-1):
        if g_in[ga]==False:
            answer+=1
            g_in[ga]=True
            go=True

            break
    if go==False:
        break
print(answer)

논리적으로는 크게 흠잡을 게 없어보입니다.

비행기를 순서대로 받되,

비행기 최대 값부터 하나씩 받는다.

g_in(gate에 비행기가 들어간 여부를 나타내는 리스트)를 탐색.

gi부터 작은 순서대로 탐색하여

비어있는 걸 보면 넣고 더한다.

만약에 안 넣었다면 다음 비행기는 못들어가므로

비행장 패쇄.

 

이 코드로 제출하면

31%대에서 시간초과가 발생합니다.

그 이유는 for문을 2개나 썼기 때문에

시간이 많이 소요가 된다는 것.

최대부터 하나씩 내려가면

이런 케이스에서 시간이 엄청 걸립니다.

 

예를들어 gate가 10000개가 있고

plane이 10000개가 있습니다.

plane입력받은 값들이

전부 10000입니다.

그러면 프로그램은은

10^5(factorial(10^5))을 돌아야합니다.

엄청난 시간이 소요가 되겠지요?

 

이 문제를 재귀함수로 풀 수 가 있었습니다.

gate 최대값을 기준으로

그래프를 탐색하면서

시간을 세이브할 수 있습니다.

이 방식대로 한다면

위의 경우처럼

모든 케이스를 전부 다 굳이 구할 필요는 없어집니다.

 

#백준 10775번 공항
import sys
sys.setrecursionlimit(100000)

G=int(input())
P=int(input())
gate=[i for i in range(G+1)]

planes=[]
for _ in range(P):
    g=int(input())
    planes.append(g)

answer=0
def find(num):
    if gate[num]==num:
        return num

    gate[num]=find(gate[num])
    return gate[num]

for gi in planes:
    tmp=find(gi)

    if tmp==0:
        break
    gate[tmp]=gate[tmp-1]
    answer+=1



print(answer)

 

재귀함수를 쓰면서

for문을 줄일 수 있음을 상시시켜주는 좋은 문제입니다.

(힌트얻고 이해가 안가서

종이에 직접 그려도 봤습니다.

이런 그래프 탐색이 아직도 많이 어렵네요.

차근차근 눈으로 보면서

머릿속에 박아야할 듯 합니다.)