[백준 7568번] 덩치 - python

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

📌 문제 탐색하기

목표

• 몸무게와 키를 비교하여 덩치 등수 매기기
• 몸무게와 키 모두가 커야지 등수가 더 높다.

입력값

• 첫 줄에는 전체 사람의 수 N이 입력된다. (2 ≤ N ≤ 50)
• N개의 줄에 각 사람의 몸무게와 키가 양의 정수로 공백을 두고 주어진다. (10 ≤ x, y ≤ 200)
  • ex)
  • 5 55 185 58 183 88 186 60 175 46 155

출력값

• 나열된 사람의 덩치 등수를 구해서 입력된 순서대로 등수를 한 줄로 출력한다.
  • ex)
  • 2 2 1 2 5

📌 코드 설계하기

해결 아이디어

• 입력을 받으면서 비교를 해야할까 먼저 고민을 했다. 근데 입력을 받으면서 비교하려면 처음 입력된 사람의 키 몸무게는 비교할 대상이 없어서 나중에 다시 비교를 하려면 계산량이 많아질 것이라는 생각이 들었다.
• 먼저 입력을 다 받고 2중 for문을 돌면서 등수를 계산하자.
• reward 배열을 하나 더 만들어서 몸무게와 키 모두가 다른 사람보다 작을 때 reward에 1을 더해주자. 그러면 동일 등수도 나올 수 있을 것이다.

📌 정답 코드

import sys

n = int(sys.stdin.readline())
reward = [1] * n
wh_list = []
for i in range(n):
    wh_list.append(list(map(int, input().split())))

for i in range(n-1):
    for j in range (i+1, n):
        if wh_list[i][0] < wh_list[j][0] and wh_list[i][1] < wh_list[j][1]:
            reward[i] += 1
        elif wh_list[i][0] > wh_list[j][0] and wh_list[i][1] > wh_list[j][1]:
            reward[j] += 1

print(*reward)

시간 복잡도 계산해보기

• 입력 처리
  • int(sys.stdin.readline()) → O(1)
  • wh_list.append(list(map(int, input().split()))) * n → O(N)
  • reward = [1] * n → O(N)
  • 합치면 → O(N)
• for문
  • 이중 for문 → O($N^2$)
• 출력 처리
  • n 길이의 배열 출력 → O(N)

최종 시간 복잡도: O($N^2$)