[Python/파이썬] 백준 알고리즘 7568번 - 덩치

브루트 포스 유형 문제이다.

 

 

 

<풀이>

N = int(input())
sizeList = []

for _ in range(N):
    x, y = map(int, input().split())
    sizeList.append((x, y))

for size in sizeList:
    rank = 1
    for compare_size in sizeList:
        if size[0] < compare_size[0] and size[1] < compare_size[1]:
            rank += 1
    print(rank, end=' ')

처음엔 너무 어렵게 접근했다.

사실은 문제에 답이 있었다. 바로 "N명의 집단에서 각 사람의 덩치 등수는 자신보다 더 "큰 덩치"의 사람의 수로 정해진다." 라는 문장에 답이 있었다.
그냥 간단하게 자기보다 몸무게와 키가 둘다 더 큰, 자신보다 덩치가 더 큰 사람의 수가 덩치 등수가 되는 것이었다.

 

코드를 보면 덩치의 데이터들을 리스트로 받아줄 sizeList 변수를 만들었다. 그리고 데이터를 tuple 형태로 모두 받는다.

그리고 브루트 포스 유형의 문제답게 리스트의 전체 element들을 확인한다.

for문을 통해 하나씩 덩치 데이터를 뽑고, 리스트의 다른 전체 덩치들과 비교해 자신보다 "큰 덩치"가 몇명이나 있는지 구한다. (if size[0] < compare_size[0] and size[1] < compare_size[1]:)

그리고 만약 덩치가 더 크다면 rank를 +1한다.

초기 rank 값이 1인 이유는 자신보다 더 큰 덩치가 없는 사람도 덩치 등수는 0이 아니라 1이기 때문이다. 때문에 자신보다 큰 덩치 수 + 1을 해줘야 덩치 등수가 나오는 것이다.

 

 

 

<핵심 정리>

1. 등수 중복을 허락한 등수 문제의 경우 자신 보다 큰 element들의 개수만 세주면 된다. 그것이 등수와 관련이 있다.

2. 복잡해질수록 간단하게 생각하자.