[서로소집합] CCC '탑승구' (Python)

<문제>

공항에는 G개의 탑승구가 있으며, 각각의 탑승구는 1번부터 G번까지의 번호로 구분됩니다.

공항에는 P개의 비행기가 차례대로 도착할 예정이며, i번째 비행기를 1번부터 g(i) 번째 (1 <=g(i)<G) 탑승구 중 하나에 영구적으로 도킹해야 합니다. 이때, 다른 비행기가 도킹하지 않은 탑승구에만 도킹할 수 있습니다.

또한 P개의 비행기를 순서대로 도킹하다가 만약에 어떠한 탑승구에도 도킹할 수 없는 비행기가 나오는 경우, 그 시점에서 공항의 운행을 중지합니다. 공항의 관리자는 최대한 많은 비행기를 공항에 도킹하고자 합니다. 비행기를 최대 몇 대 도킹할 수 있는지를 출력하는 프로그램을 작성하세요.

 

<입력 조건>

• 첫째 줄에는 탑승구의 수 G(1<=G<=100,000)가 주어집니다.
• 둘째 줄에는 비행기의 수 P(1<=P<=100,000)가 주어집니다.
• 다음 P개의 줄에는 각 비행기가 도킹할 수 있는 탑승구의 정보 g(i)(1 <=g(i)<=G)가 주어집니다. 이는 i번째 비행기가 1번부터 g(i) 번째 (1 <=g(i)<=G)  탑승구 중 하나에 도킹할 수 있다는 의미입니다.

<출력 조건>

• 첫째 줄에 도킹할 수 있는 비행기의 최대 개수를 출력합니다.

---

<문제 풀이>

• 일단, 비행기 번호에 맞는 탑승구에 도킹한다
• 도킹할 수 없으면 비행기 번호-1의 탑승구에 도킹 할 수 있는지 확인한다.
• 탑승구가 0이 될 때까지 도킹하지 못하면 공항 운행을 중지시키고 도킹한 개수를 출력한다.

<코드>

'''입력예시
4
3
4
1
1

4
6
2
2
3
3
4
4
'''

g = int(input())
p = int(input())
gate = [0]*(g+1)
cnt = 0
for i in range(p):
    air = int(input())
    brk = 0
    for a in range(air, 0, -1):
        if gate[a] == 0:
            gate[a] = air
            cnt += 1
            break
        else:
            brk += 1
    if brk==air:
        break
print(cnt)

#이취코 답
def find_parent(parent,x):
	if parent[x] != x:
    	parent[x] = find_parent(parent, parent[x])
    return parent[x]
    
def union_parent(parent,a,b):
	a = find_parent(parent,a)
    b = find_parent(parent,b)
	if a<b:
    	parent[b] = a
    else:
    	parent[a] = b
        
g = int(input())
p = int(input())
parent = [0] * (g+1)

for i in range(1,g+1):
	parent[i] = i
    
result = 0
for _ in range(p):
	data = find_parent(parent,int(input()))
    if data == 0:
    	break
    union_parent(parent,data,data-1)
    result += 1
    
print(result)

#220406
g = int(input())
p = int(input())

def find_parent(parent,x):
    if parent[x]!=x:
        parent[x] = find_parent(parent,parent[x])
    return parent[x]

def union_parent(parent,a,b):
    a = find_parent(parent,a)
    b = find_parent(parent,b)
    if a<b:
        parent[b] = a
    else:
        parent[a] = b
        
parent = [0]*(g+1)
for i in range(g+1):
    parent[i] = i
    
answer = 0

for _ in range(p):
    tmp = find_parent(parent, int(input()))
    if tmp == 0:
        break
    tmp = union_parent(parent, tmp, tmp - 1)
    answer += 1
    
print(answer)

 

<고쳐야 할 점>

• 서로소 집합 알고리즘으로도 풀 수 있음