백준 온라인 저지, 분리집합 / 10775번: 공항 (파이썬 / 백준 골드문제)

문제

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

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

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

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

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

입력

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

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

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

출력

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

제한

예제 입력 1

4
3
4
1
1

예제 출력 1

2

예제 입력 2

4
6
2
2
3
3
4
4

예제 출력 2

3

힌트

예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다.

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

 

W3sicHJvYmxlbV9pZCI6IjEwNzc1IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVhY2Y1XHVkNTZkIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM2MjRcdWIyOThcdWM3NDAgXHVjMmUwXHVjMmI5XHVjNmQwXHVjNzU4IFx1YzBkZFx1Yzc3Y1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYzE1XHVjMmI5XHVjNmQwXHVjNzQwIFx1YzBkZFx1Yzc3Y1x1Yzc0NCBcdWI5ZGVcdWM1NDQgXHVjMmUwXHVjMmI5XHVjNmQwXHVjNWQwXHVhYzhjIFx1Yzc3OFx1Y2M5Y1x1YWQ2ZFx1YzgxY1x1YWNmNVx1ZDU2ZFx1Yzc0NCBcdWMxMjBcdWJiM2NcdWI4NWMgXHVjOTJjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjZjVcdWQ1NmRcdWM1ZDBcdWIyOTQgR1x1YWMxY1x1Yzc1OCBcdWFjOGNcdWM3NzRcdWQyYjhcdWFjMDAgXHVjNzg4XHVjNzNjXHViYTcwIFx1YWMwMVx1YWMwMVx1Yzc0MCAxXHVjNWQwXHVjMTFjIEdcdWFlNGNcdWM5YzBcdWM3NTggXHViYzg4XHVkNjM4XHViOTdjIFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWNmNVx1ZDU2ZFx1YzVkMFx1YjI5NCBQXHVhYzFjXHVjNzU4IFx1YmU0NFx1ZDU4OVx1YWUzMFx1YWMwMCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHViM2M0XHVjYzI5XHVkNTYwIFx1YzYwOFx1YzgxNVx1Yzc3NFx1YmE3MCwgXHViMmY5XHVjMmUwXHVjNzQwIGlcdWJjODhcdWM5ZjggXHViZTQ0XHVkNTg5XHVhZTMwXHViOTdjIDFcdWJjODhcdWJkODBcdWQxMzAgZzxzdWI+aTxcL3N1Yj4gKDEgJmxlOyBnPHN1Yj5pPFwvc3ViPiAmbGU7IEcpIFx1YmM4OFx1YzlmOCBcdWFjOGNcdWM3NzRcdWQyYjhcdWM5MTEgXHVkNTU4XHViMDk4XHVjNWQwIFx1YzYwMVx1YWQ2Y1x1YzgwMVx1YzczY1x1Yjg1YyBcdWIzYzRcdWQwYjlcdWQ1NThcdWI4MjQgXHVkNTVjXHViMmU0LiBcdWJlNDRcdWQ1ODlcdWFlMzBcdWFjMDAgXHVjNWI0XHViMjkwIFx1YWM4Y1x1Yzc3NFx1ZDJiOFx1YzVkMFx1YjNjNCBcdWIzYzRcdWQwYjlcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YjJlNFx1YmE3NCBcdWFjZjVcdWQ1NmRcdWM3NzQgXHVkM2QwXHVjMWM0XHViNDE4XHVhY2UwLCBcdWM3NzRcdWQ2YzQgXHVjNWI0XHViNWE0IFx1YmU0NFx1ZDU4OVx1YWUzMFx1YjNjNCBcdWIzYzRcdWNjMjlcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMmUwXHVjMmI5XHVjNmQwXHVjNzQwIFx1YWMwMFx1YzdhNSBcdWI5Y2VcdWM3NDAgXHViZTQ0XHVkNTg5XHVhZTMwXHViOTdjIFx1YWNmNVx1ZDU2ZFx1YzVkMCBcdWIzYzRcdWQwYjlcdWMyZGNcdWNmMWNcdWMxMWMgXHViYzE1XHVjMmI5XHVjNmQwXHVjNzQ0IFx1ZDU4OVx1YmNmNVx1ZDU1OFx1YWM4YyBcdWQ1NThcdWFjZTAgXHVjMmY2XHVjNWI0XHVkNTVjXHViMmU0LiBcdWMyYjlcdWM2ZDBcdWM3NzRcdWIyOTQgXHViZTQ0XHVkNTg5XHVhZTMwXHViOTdjIFx1Y2Q1Y1x1YjMwMCBcdWJhODcgXHViMzAwIFx1YjNjNFx1ZDBiOVx1YzJkY1x1ZDBhYyBcdWMyMTggXHVjNzg4XHViMjk0XHVhYzAwPzxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzhjXHVjNzc0XHVkMmI4XHVjNzU4IFx1YzIxOCBHICgxICZsZTsgRyAmbGU7IDEwPHN1cD41PFwvc3VwPilcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NTAgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWJlNDRcdWQ1ODlcdWFlMzBcdWM3NTggXHVjMjE4IFAgKDEgJmxlOyBQICZsZTsgMTA8c3VwPjU8XC9zdXA+KVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1ZDZjNCBQXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBnPHN1Yj5pPFwvc3ViPiAoMSAmbGU7IGc8c3ViPmk8XC9zdWI+ICZsZTsgRykgXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWMyYjlcdWM2ZDBcdWM3NzRcdWFjMDAgXHViM2M0XHVkMGI5XHVjMmRjXHVkMGFjIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjZDVjXHViMzAwXHVjNzU4IFx1YmU0NFx1ZDU4OVx1YWUzMCBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWM2MDhcdWM4MWMgMSA6IFsyXVs/XVs/XVsxXSBcdWQ2MTVcdWQwZGNcdWI4NWMgXHViM2M0XHVkMGI5XHVjMmRjXHVkMGFjIFx1YzIxOCBcdWM3ODhcdWIyZTQuIDNcdWJjODhcdWM5ZjggXHViZTQ0XHVkNTg5XHVhZTMwXHViMjk0IFx1YjNjNFx1ZDBiOVx1YzJkY1x1ZDBhYyBcdWMyMTggXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWM4MWMgMiA6IFsxXVsyXVszXVs/XSBcdWQ2MTVcdWQwZGNcdWI4NWMgXHViM2M0XHVkMGI5IFx1YzJkY1x1ZDBhYyBcdWMyMTggXHVjNzg4XHVhY2UwLCA0XHViYzg4XHVjOWY4IFx1YmU0NFx1ZDU4OVx1YWUzMFx1YjI5NCBcdWM4MDhcdWIzMDAgXHViM2M0XHVkMGI5IFx1YzJkY1x1ZDBhYyBcdWMyMTggXHVjNWM2XHVjNWI0XHVjMTFjIFx1Yzc3NFx1ZDZjNCBcdWNkOTRcdWFjMDBcdWM4MDFcdWM3NzggXHViM2M0XHVkMGI5XHVjNzQwIFx1YmQ4OFx1YWMwMFx1YjJhNVx1ZDU1OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIxMDc3NSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkdhdGVzIiwiZGVzY3JpcHRpb24iOiI8cD5Gb3IgeW91ciBiaXJ0aGRheSwgeW91IHdlcmUgZ2l2ZW4gYW4gYWlycG9ydC48XC9wPlxyXG5cclxuPHA+VGhlIGFpcnBvcnQgaGFzIEcgZ2F0ZXMsIG51bWJlcmVkIGZyb20gMSB0byBHLjxcL3A+XHJcblxyXG48cD5QIHBsYW5lcyBhcnJpdmUgYXQgdGhlIGFpcnBvcnQsIG9uZSBhZnRlciBhbm90aGVyLiBZb3UgYXJlIHRvIGFzc2lnbiB0aGUgaXRoIHBsYW5lIHRvIHBlcm1hbmVudGx5IGRvY2sgYXQgYW55IGdhdGUgMSwgLiAuIC4gLCBnPHN1Yj5pPFwvc3ViPiAoMSAmbGU7IGc8c3ViPmk8XC9zdWI+ICZsZTsgRyksIGF0IHdoaWNoIG5vIHByZXZpb3VzIHBsYW5lIGhhcyBkb2NrZWQuIEFzIHNvb24gYXMgYSBwbGFuZSBjYW5ub3QgZG9jayBhdCBhbnkgZ2F0ZSwgdGhlIGFpcnBvcnQgaXMgc2h1dCBkb3duIGFuZCBubyBmdXR1cmUgcGxhbmVzIGFyZSBhbGxvd2VkIHRvIGFycml2ZS48XC9wPlxyXG5cclxuPHA+SW4gb3JkZXIgdG8ga2VlcCB0aGUgcGVyc29uIHdobyBnYXZlIHlvdSB0aGUgYWlycG9ydCBoYXBweSwgeW91IHdvdWxkIGxpa2UgdG8gbWF4aW1pemUgdGhlIG51bWJlciBvZiBwbGFuZXMgc3RhcnRpbmcgZnJvbSB0aGUgYmVnaW5uaW5nIHRoYXQgY2FuIGFsbCBkb2NrIGF0IGRpZmZlcmVudCBnYXRlcy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIEcgKDEgJmxlOyBHICZsZTsgMTA8c3VwPjU8XC9zdXA+KSwgdGhlIG51bWJlciBvZiBnYXRlcyBhdCB0aGUgYWlycG9ydC48XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIFAgKDEgJmxlOyBQICZsZTsgMTA8c3VwPjU8XC9zdXA+KSwgdGhlIG51bWJlciBvZiBwbGFuZXMgd2hpY2ggd2lsbCBsYW5kLjxcL3A+XHJcblxyXG48cD5UaGUgbmV4dCBQIGxpbmVzIGNvbnRhaW4gb25lIGludGVnZXIgZzxzdWI+aTxcL3N1Yj4gKDEgJmxlOyBnPHN1Yj5pPFwvc3ViPiAmbGU7IEcpLCBzdWNoIHRoYXQgdGhlIGl0aCBwbGFuZSBtdXN0IGRvY2sgYXQgc29tZSBnYXRlIGZyb20gMSB0byBnPHN1Yj5pPFwvc3ViPiwgaW5jbHVzaXZlLjxcL3A+XHJcblxyXG48cD5Ob3RlIHRoYXQgZm9yIGF0IGxlYXN0IDQwJSBvZiB0aGUgbWFya3MgZm9yIHRoaXMgcXVlc3Rpb24sIFAgJmxlOyAyMDAwIGFuZCBHICZsZTsgMjAwMC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdGhlIG1heGltdW0gbnVtYmVyIG9mIHBsYW5lcyB0aGF0IGNhbiBsYW5kIHN0YXJ0aW5nIGZyb20gdGhlIGJlZ2lubmluZy48XC9wPlxyXG4iLCJoaW50IjoiPHA+RXhwbGFuYXRpb24gb2YgT3V0cHV0IGZvciBTYW1wbGUgSW5wdXQgMTxcL3A+XHJcblxyXG48cD5UaGUgZmlyc3QgcGxhbmUgY2FuIGdvIGFueXdoZXJlLCBidXQgaXQgaXMgYmVzdCB0byBub3QgcHV0IGl0IGludG8gR2F0ZSAxLiBOb3RpY2UgdGhhdCBwbGFuZXMgMiBhbmQgMyBib3RoIHdhbnQgdG8gZG9jayBpbnRvIEdhdGUgMSwgc28gcGxhbmUgMyBpcyB1bmFibGUgdG8gZG9jay48XC9wPlxyXG5cclxuPHA+RXhwbGFuYXRpb24gb2YgT3V0cHV0IGZvciBTYW1wbGUgSW5wdXQgMjxcL3A+XHJcblxyXG48cD5UaGUgZmlyc3QgdHdvIHBsYW5lcyB3aWxsIGRvY2sgaW4gZ2F0ZXMgMSBhbmQgMiAoaW4gYW55IG9yZGVyKS4gVGhlIHRoaXJkIHBsYW5lIG11c3QgZG9jayBhdCBHYXRlIDMuIFRodXMsIHRoZSBmb3VydGggcGxhbmUgY2Fubm90IGRvY2sgYW55d2hlcmUsIGFuZCB0aGUgYWlycG9ydCBpcyBjbG9zZWQsIGV2ZW4gdGhvdWdoIHBsYW5lIDUgd291bGQgaGF2ZSBiZWVuIGFibGUgdG8gZG9jay48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

접근 방법

- 분리집합을 활용해 문제를 해결한다.
- 게이트만큼의 리스트를 해당 리스트의 번호로 값을 초기화한다.
- 비행기에 대한 정보를 하나씩 탐색하며 게이트에 비행기가 도착하게 될 경우 해당 게이트의 번호와 값이 같다면 해당 게이트에서 본인보다 낮은 곳의 인덱스를 가리키게 한다.
- 게이트의 번호가 다르다면 부모 인덱스로 이동한 뒤, 해당 리스트의 값은 그 이전 인덱스를 가리킨다.
- 만약 이전 인덱스가 0이 나올 경우 탐색을 멈추고 비행기의 도킹 횟수를 출력한다.

코드

# https://www.acmicpc.net/problem/10775
# 접근 방법
# 분리집합을 활용해 문제를 해결한다.
# 게이트만큼의 리스트를 해당 리스트의 번호로 값을 초기화한다.
# 비행기에 대한 정보를 하나씩 탐색하며 게이트에 비행기가 도착하게 될 경우 해당 게이트의 번호와 값이 같다면 해당 게이트에서 본인보다 낮은 곳의 인덱스를 가리키게 한다.
# 게이트의 번호가 다르다면 부모 인덱스로 이동한 뒤, 해당 리스트의 값은 그 이전 인덱스를 가리킨다.
# 만약 이전 인덱스가 0이 나올 경우 탐색을 멈추고 비행기의 도킹 횟수를 출력한다.
def get_parent(a):
    if gate[a] == a:
        return a
    parent = get_parent(gate[a])
    gate[a] = parent
    return parent

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

g = int(input())
p = int(input())
gate = [i for i in range(g+1)]
plane = [int(input()) for _ in range(p)]
count = 0
for x in plane:
    value = get_parent(x)
    if value == 0:
        break
    count += 1
    gate[value] = value - 1
print(count)