[Python] Softeer 우물 안 개구리

[Python] Softeer 우물 안 개구리

https://softeer.ai/app/assessment/index.html?xid=41519&xsrfToken=xC6choSqjtruvFxTqUYTPcNygjlCydkM&testType=practice

Candidate | Softeer Assessment UI

 

문제

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

제약조건

2 ≤ N ≤ 105
1 ≤ M ≤ 105
1 ≤ Wi ≤ 109
1 ≤ Aj, Bj ≤ N
Aj ≠ Bj

입력형식

첫 번째 줄에 두 정수 N, M이 주어진다.
두 번째 줄에 N개의 정수 W1, W2, ... , WN 이 주어진다.

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

출력형식

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

입력예제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

구현코드

import sys
import copy

# 입력 받기
total_members, relations = map(int, sys.stdin.readline().split())
weight_list = list(map(int, sys.stdin.readline().split()))
check = [1] * total_members  # 각 회원이 최고로 생각하는지 여부를 나타내는 리스트

# 친분관계 입력 받고, 최고로 생각하는 회원 체크
for _ in range(relations):
    a, b = map(int, sys.stdin.readline().split())
    
    # 만약 a가 무게가 더 작거나 같으면 a는 최고가 아님
    if weight_list[a - 1] <= weight_list[b - 1]:
        check[a - 1] = 0
    
    # 만약 b가 무게가 더 작거나 같으면 b는 최고가 아님
    if weight_list[b - 1] <= weight_list[a - 1]:
        check[b - 1] = 0

# 최고로 생각하는 회원의 수 출력
print(sum(check))

 

설명

- 그리디
- 각 회원을 한 번씩 검사하면서 친분관계를 확인하고, 무게 비교를 통해 해당 회원이 최고로 생각하는 회원을 판단하는 방식

- 시간복잡도:  O(N + M) , N은 회원 수  M은 친분관계의 수