[백준/Python] 10865번 친구 친구

 

https://www.acmicpc.net/problem/10865

10865번: 친구 친구

문제분석
친구 관계가 주어진다. 예를 들어 1번과 2번이 친구면 1 2가 주어진다.
입력으로 자기자신과 친구인 경우(ex 1 1)와 전에 나온 친구관계는 나오지 않는다(ex 1 2이 나온경우 2 1은 입력으로 주어지지 않음).
1번 사람부터 N번 사람까지 친구가 몇명 있는지 출력한다.

문제풀이
처음에는 친구관계를 나타내는 표를 생각해서 2차원 배열을 생각했다. 그리고 1 1 같은 경우는 나오지 않는다고해서 2차원 배열을 만들고 행으로 한번 훑고 열로 한번 훑어서 더하면 모든 친구수가 나오겠구나 하고 2차원 배열로 짰다.

input = __import__('sys').stdin.readline

N, M = map(int, input().strip().split())

friend = [[0]*M for _ in range(M)]


for m in range(M):
    a, b = map(int, input().split())
    friend[a-1][b-1] = 1

num = [0] * N

for n in range(N):
    for e in friend[n]:
        if e == 1: num[n]+=1

for n in range(N):
    for row in friend:
        if row[n] == 1: num[n]+=1

for n in num: print(n)

하지만 이 경우 N이 최대 1e+8이기 때문에 최대 8e+16의 메모리 공간을 차지하게 되어 문제의 메모리 조건인 2.56e+8을 초과하게 된다. 따라서 메모리초과 오류가 발생하였다.

친구관계에 대한 표를 만드는 것보다 더 단순하게, 1차원배열을 만들어서 그냥 친구가 나오면 친구수를 +1하면 된다. 똑같은 친구 관계가 순서가 바꿔서 나오는 경우가 없으므로 가능하다. 

input = __import__('sys').stdin.readline

N, M = map(int, input().strip().split())

num = [0] * N
for m in range(M):
    a, b = map(int, input().strip().split())
    num[a-1] += 1
    num[b-1] += 1
    
for n in num: print(n)