[python/백준] 7568. 덩치(S5)

📌 문제 탐색하기

👉 문제바로가기
N: 전체 사람의 수(2 ≤ N ≤ 50)
x, y: 각 사람의 몸무게와 키를 나타내는 양의 정수(10 ≤ x, y ≤ 200)

몸무게와 키를 모두 받아야하기 때문에 2차원 리스트를 활용하면 되겠네요. 최종적으로 덩치 등수를 출력하기위해 등수를 담을 리스트(grade)를 하나 더 정의합니다. 키와 몸무게 모두 자신보다 큰 원소가 몇개인지 판단해서 등수를 구한 후 리스트(grade)에 넣으면 될 것 같습니다.

알고리즘 선택

몸무게와 키에 대해 모든 원소값을 비교해야 하므로 브루트포스 알고리즘을 사용합니다.

가능한 시간복잡도

전체 사람 수의 최댓값은 50이므로 사람 수가 최대라고 가정해도 연산 횟수는 50*50 = 2500회이므로 1초 안에 충분히 연산이 가능합니다.

📌 코드 설계하기

1. 전체 사람의 수(N)에 대한 Input을 받습니다.
2. N명만큼의 몸무게, 키 값 쌍을 Input받아 해당 데이터로 2차원 리스트를 생성합니다.
3. 몸무게와 키 값을 비교하여 두 값이 모두 큰 요소의 갯수(count)를 구합니다.
4. count로부터 등수를 계산하여 등수 리스트에 담고, 해당 리스트 원소를 차례대로 출력합니다.

📌 정답 코드

import sys

N = int(sys.stdin.readline())
physical = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
grade = []  #등수

for i in range(N):
  count = 0
  for j in range(N):
  	# 키와 몸무게 비교
    if ((physical[i][0] < physical[j][0])
        and (physical[i][1] < physical[j][1])):
      count += 1
  grade.append(count + 1)    # 등수 = 나보다 키, 몸무게 값이 큰 사람 수(count)  + 1

print(*grade)