[백준][10775][Python 파이썬][G2] 공항

문제

오늘은 신승원의 생일이다.

박승원은 생일을 맞아 신승원에게 인천국제공항을 선물로 줬다.

공항에는 G개의 게이트가 있으며 각각은 1에서 G까지의 번호를 가지고 있다.

공항에는 P개의 비행기가 순서대로 도착할 예정이며, 당신은 i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다. 비행기가 어느 게이트에도 도킹할 수 없다면 공항이 폐쇄되고, 이후 어떤 비행기도 도착할 수 없다.

신승원은 가장 많은 비행기를 공항에 도킹시켜서 박승원을 행복하게 하고 싶어한다. 승원이는 비행기를 최대 몇 대 도킹시킬 수 있는가?

입력

첫 번째 줄에는 게이트의 수 G (1 ≤ G ≤ 105)가 주어진다.

두 번째 줄에는 비행기의 수 P (1 ≤ P ≤ 105)가 주어진다.

이후 P개의 줄에 gi (1 ≤ gi ≤ G) 가 주어진다.

출력

승원이가 도킹시킬 수 있는 최대의 비행기 수를 출력한다.

 

 

테스트케이스

4 6 2 2 3 3 4 4	4 3 4 1 1	5 5 5 5 5 5 5	4 1 8 8 9 2 5 6 10 1
3	2	5	9

 

코드

import sys

input = sys.stdin.readline

sys.setrecursionlimit(int(1e5))

G = int(input())

P = int(input())

Docked = [*range(G+1)]

def findgate(a):

    if a == Docked[a]:

        return a

    Docked[a] = findgate(Docked[a])

    return Docked[a]

ans = 0

closed = False

for i in range(P):

    airplane = int(input())

    if closed:

        continue

    lastdocked = findgate(airplane)

    if not lastdocked == 0:

        ans += 1

        Docked[lastdocked] = lastdocked-1

    else:

        closed = True

        continue

print(ans)

 

후기

제일처음에 그냥 그리디네? 하고 풀었다가 시간초과 오질라게 나고....

좀 메모이제이션? 느낌으로 같은 번호 지정했는데 시간초과 나고...

배열에서 특정부분의 최솟값 느낌으로 했는데 시간초과 나고.. (이건 나중에 세그먼트 트리 공부하면 될수도 있지 않을까?)

분리집합이라는 말을 어쩌다 보게돼서 분리집합으로 구현하니까? 오히려 좀더 막막하고.. 

보다가 그 아이디어만 떠올려서 그 번호에서 갔던 가장 작은 부분을 기록하자! 같은 느낌으로 구현해내는데

pypy 재귀 한계에 걸려서 sys로 재귀한계 늘리니까 메모리초과 바로 떠버리고

pypy가 재귀에 약하다는걸 그때서야 기억해내고 파이썬으로 옮겨서 맞았다

여러분들은 pypy쓰는거 버릇들이지 마십쇼...