[Softeer]우물 안 개구리 파이썬 풀이
Softeer 우물 안 개구리¶
문제 page: https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=394
관계에 따라 자신의 무게와 max(타인의 무게)를 비교하여 결과값을 도출해내는 문제이다.
즉 A_j가 알고 있는 다른 회원의 무게가 [a, b, c]일 때,
if weight[A_j] <= max(a, b, c):
result -= 1
이에 적합한 자료형은 dict형이다.
{
A_j = [weight[B_j], weight[B_j], ...]
}
이 때 주의해야할 점은 친분관계는 양방향이라는 점이다.
문제에서 특별히 누구와도 친분이 없는 멤버의 경우 본인이 최고라고 생각하므로 이에 대한 경우도 생각해줘야 한다.
In [2]:
N, M = [int(x) for x in input().split()]
weights = [int(weight) for weight in input().split()]
weights.insert(0, -1) # Not use 0 index
count = N
relation = {}
for i in range(1, N+1):
relation[i] = []
for _ in range(M):
A_j, B_j = [int(x) for x in input().split()]
relation[A_j].append(weights[B_j])
relation[B_j].append(weights[A_j])
for i in range(1, N+1):
if relation[i] == []:
continue
if weights[i] <= max(relation[i]):
count -= 1
print(count)
5 3 1 2 3 4 5 1 3 2 4 2 5 3