[softeer] 소프티어(파이썬): 우물 안 개구리 ★★★

문제

Softeer

- 헬스장에는 N명의 회원이 있고 회원은 1부터 N사이의 번호가 부여된다.

- I번 회원이 들 수 있는 역기의 무게는 W(i)이다. 즉, 자신의 번호와 같은 곳에 있는 역기를 들 수 있다.

- 회원들 사이에는 M개의 친분 관계 (A, B)가 있다. (A, B)는 A회원과 B회원이 친분 관계임을 의미한다.

-  I번 회원은 자신과 친분관계가 있는 다른 회원보다 들 수 있는 역기의 무게가 무거우면 자신이 최고라고     생각한다.

- 헬스장에서 자신이 최고라고 생각하는 회원이 몇 명인지 구하는 문제이다.

- 입력은 다음 조건을 만족한다.

- 헬스장 회원이 N명일때 2 ≤ N ≤ 10^5인 정수이다.

- 친분 관계의 수가 M일때 1 ≤ M ≤ 10^5인 정수이다.

- 역기의 무게가 W일때  1 ≤ W ≤ 10^9인 정수이다.

- 친분 관계(A, B)가 있을 때  1 ≤ A, B ≤ N ,  A ≠ B을 만족한다.

알고리즘

- 헬스장의 회원수와 친분관계의 수를 입력받는다.

- 역기의 무게를 입력받아 리스트 변수에 넣는다.

- 친분 관계를 반복문을 이용하여 입력받아 리스트 변수에 넣는다.

- 0이 들어간 리스트를 회원수보다 +1개만큼 만들어 리스트 변수에 넣는다.

- 반복문과 조건문을 통해 더 무거운 무게를 들 수 있는지 비교한다.

- 더 무거운 무게를 들 수 없다면 0을 부여하여 구분한다.

- 리스트에서 1인 수만큼 이 자신이 최고라고 하는 회원 수 이기 때문에 리스트에서 1인 수를 출력한다.

코드

import sys

n, m = map(int, sys.stdin.readline().split())
w = list(map(int, sys.stdin.readline().split()))
g = [list(map(int, sys.stdin.readline().split())) for x in range(m)]

# [0] 리스트를 n+1개 만큼 만든다.
# 순서를 구분하기 위해 0번째의 수에 0을 넣어 제외한다.
cnt = [1 for _ in range(n+1)]
cnt[0]=0

# 그룹 수 만큼 반복한다.
# A,B가 들 수 있는 무게를 g 리스트에서 가져와 w에 넣어 비교한다.
# 비교할때 더 무거운 무게를 들 수 없다면 0을 부여한다.
for i in range(m):
    if w[g[i][0]-1] > w[g[i][1]-1]:
            cnt[g[i][1]] = 0

    elif w[g[i][0]-1] < w[g[i][1]-1]:
            cnt[g[i][0]] = 0

	# 똑같은 무게를 들 수 있다면 둘다 0을 부여
    else:
        cnt[g[i][0]] = 0
        cnt[g[i][1]] = 0


# cnt 리스트에 1의 개수를 출력한다.
print(cnt.count(1))

결과

위 코드 밑에 print(cnt)를 작성하여 자신이 최고라고 생각하는 회원의 수를 확인해보면 다음 출력 화면과 같이 나온다.

<출력화면>

(편의상 무게의 단위는 kg으로 가정하겠다.) 위 출력 화면을 보게 되면 1번 회원은 1kg을 들 수 있고 3번 회원은 3kg을 들 수 있기 때문에 1번 회원은 자신이 최고라고 생각하지 않아 0을 부여한 것이다. 다음으로 2번 회원은 2kg을 들 수 있고 4번 회원은 4kg을 들 수 있기 때문에 2번 회원은 자신이 최고라고 생각하지 않아 0을 부여한다. 또 2번 회원과 5번 회원을 비교하면 5번 회원은 5kg을 들 수 있기 때문에 5번 회원은 자신이 최고라고 생각한다. 

<출력화면>

위 다른 예시의 출력 화면을 보게 되면 1번 회원은 7kg을 들 수 있고 3번 회원도 7kg을 들 수 있기 때문에 서로 같은 무게를 드는 경우에는 자신이 최고라고 생각하지 않아 둘 회원 모두 0을 부여한다. 다음으로 2번 회원은 5kg을 들 수 있고 4번 회원은 8kg을 들 수 있기 때문에 2번 회원은 자신이 최고라고 생각하지 않아 0을 부여한다. 또 2번 회원과 5번 회원을 비교하면 5번 회원은 1kg을 들 수 있기 때문에 5번 회원은 자신이 최고라고 생각하지 않아 0을 부여받는다.

따라서 코드를 분석하게 되면 회원 모두 자신이 최고라고 생각한다고 가정하고 풀어야 한다. 반복문과 조건문을 통해 친분관계에서 자신보다 더 무거운 무게를 드는 회원이 한 명이라도 생길 경우 0을 부여하여 최고가 아니라는 것으로 구분하고, 또 같은 무게를 드는 경우도 서로 자신이 최고라고 생각하지 않기 때문에 둘 회원 모두 0을 부여하여 구분하는 것이다. 그렇게 리스트에 남아있는 1의 개수를 출력하면 된다.

github

junjange/CodingTest