[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