[python] 소프티어 - 우물 안 개구리

소프티어 lv.3 문제
https://softeer.ai/practice/info.do?idx=1&eid=394

언어별 시간/메모리
Python : 2초, 256MB

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

제약조건
2 ≤ N ≤ 105
1 ≤ M ≤ 105
1 ≤ $W_i$ ≤ 109
1 ≤ $A_j$, $B_j$ ≤ N
$A_j$ ≠ $B_j$

입력형식
첫 번째 줄에 두 정수 N, M이 주어진다.
두 번째 줄에 N개의 정수 $W_1$, $W_2$, ... , $W_N$ 이 주어진다.

다음 M개의 줄의 j번째 줄에는 두 정수 $A_j$, $B_j$ 가 주어진다.

출력형식
첫 번째 줄에 자신이 최고라고 생각하는 회원 수를 출력한다.

입력예제1
5 3
1 2 3 4 5
1 3
2 4
2 5
출력예제1
3

입력예제2
5 3
7 5 7 7 1
1 2
2 3
3 4
출력예제2
2

---

풀이

자신과 친분이 있는 사람보다 본인이 더 무거운 무게를 들면 자신이 최고라고 생각한다.

• 누구와도 친분이 없으면 본인이 최고라고 생각하니까 우선 모두가 본인이 최고라고 생각하도록 회원번호가 인덱스인 리스트를 1로 초기화하는 것을 떠올렸다.
• 친분관계를 받아서, 두 사람의 무게를 비교하고 본인이 상대보다 무겁게 들지 못하면 최고가 아니라고 생각하도록 둔다.

---

나의 답

n, relation = map(int, input().split()) # 회원수, 친분관계의 수

canLift = list(map(int,input().split())) # 들 수 있는 무게 입력
canLift.insert(0,0) # 회원번호와 인덱스번호를 맞추기 위함함

imBest = [0] + [1] * (n) # 인덱스0은 0설정, 나머지는 자신이 최고라고 설정

for i in range(relation):
    a, b = map(int, input().split()) # a와 b는 친분관계가 있다
    if not (canLift[a] > canLift[b]):   # a가 b보다 크지 않으면
        imBest[a] = 0 # a는 본인이 최고라고 생각하지 않는다
    if not (canLift[b] > canLift[a]):   #b가 a보다 크지 않으면
        imBest[b] = 0 # b는 본인이 최고라고 생각하지 않는다

print(imBest.count(1)) # 본인이 최고라고 생각하는 사람의 수

처음 풀어본 소프티어 레벨3문제였는데 생각보다 쉬웠다.