문제

헬스장에서 N명의 회원이 운동을 하고 있다. 각 회원은 1에서 N사이의 번호가 부여되어 있고, i번 회원이 들 수 있는 역기의 무게는 Wi이다. 회원들 사이에는 M개의 친분관계 (Aj, Bj)가 있다. (Aj, Bj)는 Aj번 회원과 Bj번 회원이 친분 관계가 있다는 것을 의미한다. i번 회원은 자신과 친분 관계가 있는 다른 회원보다 들 수 있는 역기의 무게가 무거우면 자신이 최고라고 생각한다. 단, 누구와도 친분이 없는 멤버는 본인이 최고라고 생각한다.

이 헬스장에서 자신이 최고라고 생각하는 회원은 몇 명인가?

풀이

아이디어

• 회원들의 번호에 알맞은 무게들을 weights 배열에 저장한다.
• defaultdict를 다음과 같이 활용한다.
  • 회원 i번에 대해서 이웃들의 무게들을 list로 저장한다.
• N번 반복문을 돌면서 다음 로직 수행한다.
  • i번의 이웃들의 무게들의 리스트를 defaultdict에서 가져온다.
  • i번의 무게보다 무거운 이웃이 발견되면 그 즉시 break
  • i번의 무게보다 무거운 이웃이 없다면 answer += 1

코드

import sys
from collections import defaultdict
N, M = map(int, sys.stdin.readline().split(" "))
weights = [0] + list(map(int, sys.stdin.readline().split(" ")))
graph = defaultdict(list)

for i in range(M):
  src, dest = map(int, sys.stdin.readline().split(" "))
  graph[src].append(weights[dest])
  graph[dest].append(weights[src])

answer = 0
for i in range(1, N+1):
  neighbor_weights = graph[i]
  flag = True
  for w in neighbor_weights:
    if weights[i] <= w:
      flag = False
      break

  if flag:
    answer += 1

print(answer)