백준 2458 키 순서

백준 2458번 키 순서(https://www.acmicpc.net/problem/2458)

문제 설명

• 1번 학생의 키 < 5번 학생의 키
• 3번 학생의 키 < 4번 학생의 키
• 5번 학생의 키 < 4번 학생의 키
• 4번 학생의 키 < 2번 학생의 키
• 4번 학생의 키 < 6번 학생의 키
• 5번 학생의 키 < 2번 학생의 키

위와같은 학생간의 키를 비교한 결과가 주어질 때, 자신의 키가 몇 번째인지 알 수 있는 학생들이 모두 몇 명인지 계산하여 출력하는 프로그램을 작성하시오.

주요 포인트

1. 자신의 키가 몇 번째인지 정확히 알기 위해서는, 총 인원 중 자기를 뺀 나머지 학생들이 더 큰지, 작은지 알 수 있어야 합니다.
   즉, 자신과 타 학생간의 비교 횟수가 총 학생 수에서 자신을 뺀 n-1개만큼 나오면 정확한 순서를 알 수 있다는 뜻입니다.

2. 자신보다 더 큰 아이들을 big, 작은 아이들을 small에 저장하여 마지막에 big과 small의 합이 n-1일 경우 count에 1을 더해 최종 결과를 출력합니다.

코드

import sys

n, m = map(int, sys.stdin.readline().split())
count = 0

# set을 사용해 중복 수를 막아줍니다.
big = [set() for _ in range(n + 1)]
small = [set() for _ in range(n + 1)]

for _ in range(m): #b가 a보다 크므로, a 보다 큰 b를 big[a]에, b보다 작은 a를 small[b]에 넣습니다.
    a, b = map(int, sys.stdin.readline().split())
    big[a].add(b)
    small[b].add(a)

#i보다 작다면, i보다 큰 학생들을 추가하고, i보다 크다면, i보다 작은 수들을 추가해줍니다. 
for i in range(1, n+1):
    for j in big[i]: 
        small[j].update(small[i])
    for j in small[i]:
        big[j].update(big[i])

for i in range(1, n+1): #자신보다 더 크고 작은 학생들의 합이 n-1이면 정확한 순위를 알 수 있습니다.
    if len(big[i]) + len(small[i]) == n-1:
        count += 1

print(count)

• 예시 그림
  반복문이 돌면서 위와 같이 배열이 형성 되었을 경우, 그림 위에 쓴 것 처럼 update 됩니다.
  6번보다 작은 학생은 원래 4번 하나지만, 4번보다 작은 학생이 5, 3, 1번이기에 이들을 update 해주고, 1번보다 큰 학생은 원래 5번 하나지만, 4번과 6번을 update 해주는 방식입니다.
  

생각🤔

• 플로이드 알고리즘을 이용해서도 풀 수 있는데, 방식이 다를 뿐 문제 풀이에 사용된 중요 키포인트의 본질은 동일하다고 생각하여 이렇게 풀었습니다.