[Softeer] 우물 안 개구리

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

Softeer

문제

헬스장에서 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차원배열을 선언해서 

친밀도가 있는 i,j 멤버에 대해

member[i][j] 는 j의 무게

member[j][i]는 i의 무게 이런식으로 해서 풀려고했다. 근데 N의 조건을 보니 2차원배열을 선언하면..

10^10 이 돼서 메모리가 부족하다

 

따라서 친밀관계, 들수있는 무게를 각각 입력받고

친밀관계에 따른 무게를 비교해서 한번도 진적이 없는 사람의 숫자를 출력하면 될 것 같다

 

단계별로 정리하면 아래와 같다

1. 회원수 N,M 입력받기
2. 각 회원의 역기를 들 수 있는 힘 power 입력받기
3. 친분관계를 리스트로 입력받기
4. 친분관계 인덱스로 power를 참조해서, 각 회원의 power 비교
5. 비교 후에 한번도 진적 없는 회원은 카운트

 

---

풀이코드

 

import sys #회원수 N과 친분관계 숫자 M 입력받기 N,M = map(int, sys.stdin.readline().split()) #각 회원의 power 정보 입력받기 power = list(map(int, sys.stdin.readline().split())) #친분관계 리스트 입력받기 g = [] for i in range(M):     x,y = map(int,input().split())     g.append((x,y)) # 회원정보 리스트 생성 # 친분관계가 없으면 자기가 최고인줄 알기때문에 # default 값으로 최고를 설정 # 친분관계 정보 g를 통해 최고인 멤버 구분  mem = [1] * N # 친분관계에서 누가 더 쌘지 설정 for x,y in g:     if power[x-1] > power[y-1] :         mem[y-1] = 0     elif power[x-1] < power[y-1]:         mem[x-1] = 0     else:         mem[x-1] = 0         mem[y-1] = 0 print(mem.count(1))