[Softeer][level3] 우물 안 개구리 - 파이썬(Python)

https://softeer.ai/practice/info.do?idx=1&eid=394&sw_prbl_sbms_sn=141197 

Softeer

 

 

문제

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

 

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

 

 

 

---

💡 사고 과정

굉장히 간단한문제이다. 

회원의 수 N과,  관계의수 M(간선)의 값이 10^5여서

 

O(V+E) O(2* 10^5) 정도로 계산하고 풀었다. 

 

>>> 관계의 수가 N에 비례하는게 아니고, 최대로 있어봤자 100000개이기떄문에,,

N*M은 나올수가 없으니... 고려할 필요가없다. 

 

 

결국 회원과 친분관계를 만들어주고, 친분관계에 있는 모든사람들의 weigth를 체크해 한번이라도 같거나 큰사람이 있으면 바로 반복문을 탈출시킨다. 

 

친분관계가 없는 사람은 아예반복문을 안 탈테니 바로 flag=True로 자신이 최고임을 나타낼 수 있다. 

 

마지막에 count를 출력하면 끝!

 

 

 

💻 내가 쓴 정답코드

 

import sys
input = sys.stdin.readline 

n, m = map(int,input().split())
weights = [0]+list(map(int,input().split()))
friend = [[] for _ in range(n+1)]

for _ in range(m):
    a, b = map(int,input().split())
    friend[a].append(b)
    friend[b].append(a)


count = 0

for i in range(1, n+1):
    #i번 회원은 자신과 친분관계가 있는 다른 회원 
    flag = True
    for f in friend[i]:
        if weights[i] <= weights[f]:
            flag = False
            break

    if flag==True:
        count+=1
    
print(count)