새로운 블로그로 이전 작업을 진행하고 있어 포스트가 새로 작성되고 있지 않습니다.

빠른 시일 내에 새로운 블로그로 인사드리겠습니다.

새로운 블로그 : https://unho.vercel.app/

본문 바로가기
알고리즘 문제풀이/Python

[백준] 10775 공항

by 언호 2022. 8. 26.

📖 문제


🧑🏻‍💻 풀이 과정

1) 문제 접근 및 이해

1번부터 g번째 게이트 중 하나에 도킹할 수 있으므로, g게이트부터 1번까지 도킹이 가능하다면 바로 도킹을 시도해야합니다.

 만약 g 게이트가 이미 도킹하여 사용중이라면 g 보다 작은 수 중 도킹이 가능한 가장 큰 수를 찾아야합니다.

해당 수를 찾기위해 게이트가 도킹이 되면, 다음으로 도킹이 가능한 게이트 번호를 가리키도록 하였습니다.

2) 알고리즘

  • 그리디

3) 풀이 코드

사용 언어 - Python

import sys
sys.setrecursionlimit(100000000)
sys.stdin = open('input.txt')


def union(a: int) -> int:
    '''
    게이트에 비행기 도킹

        params:
            a: 도킹 시도하려는 게이트 번호
        returns:
            a: 도킹한 게이트 번호
    '''
    a = find(a)
    li[a] = a - 1
    return a


def find(a: int) -> int:
    '''
    해당 게이트보다 작은 게이트에서 도킹이 가능한 게이트를 찾기 위해 탐색
    도킹이 가능한 게이트 번호 반환

        params:
            a: 도킹 가능 여부 확인이 필요한 게이트 번호
        returns:
            a: 도킹 가능한 게이트 번호
    '''
    if li[a] != a and a >= 0:
        li[a] = find(li[a])
        return li[a]
    return a


def solution() -> int:
    '''
    비행기가 들어오는 순서에 따라 도킹 시뮬레이션

        returns:
            ans: 도킹 가능한 최대 비행기 수
    '''
    ans = 0

    for _ in range(P):
        num = int(sys.stdin.readline())

        if union(num-1) == -1:  # 도킹한 게이트 번호가 -1이면, 불가능한 게이트이므로 종료
            break
        else:                   # 도킹 성공시 정답 1 증가
            ans += 1

    return ans


# 입력 값
G = int(sys.stdin.readline())
P = int(sys.stdin.readline())

# 도킹할 게이트들 목록
li = list(range(G))

print(solution())

🔗 문제 링크

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

 

10775번: 공항

예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불

www.acmicpc.net

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다

'알고리즘 문제풀이 > Python' 카테고리의 다른 글

[백준] 17837 새로운 게임 2  (0) 2022.08.25
[백준] 1525 퍼즐  (0) 2022.08.24
[백준] 1011 Fly me to the Alpha Centauri  (0) 2022.08.21
[백준] 2437 저울  (0) 2022.08.19
[백준] 4195 친구 네트워크  (0) 2022.08.18

댓글