[백준] 덩치

문제보기 - https://www.acmicpc.net/problem/7568

문제명    - 덩치

난이도    - S5

문제유형 - 구현

풀이일자 - 25.03.09

 

📌 문제 탐색하기

• 전체 사람의 수 N을 입력받음
  • 2 ≤ N ≤ 50
• N개의 줄에는 각 사람의 몸무게와 키를 나타내는 양의 정수 x와 y가 하나의 공백을 두고 입력받음
  • 10 ≤ x, y ≤ 200
• 두 사람을 비교하여 몸무게와 키 둘 다 더 큰 경우에만 덩치가 크다고 판단함
• 덩치 등수를 한 줄로 출력해야 함
  •  단, 공백문자로 분리되어야 함

 

🛠 시간복잡도 확인

 

• 각각의 사람을 다른 모든 사람과 비교해야 함 -> 완전탐색
• 이중 for문을 활용하기때문에 O(N²)의 시간복잡도를 가짐
• N(최대 50)이므로 O(2500) 연산으로 충분히 가능

 

📌 코드 설계하기

1. 전체 사람의 수 N 입력받기
   • int(sys.stdin.readline()) 활용
2. 몸무게, 키(x, y) 입력받기
   • [tuple(map(int, input().split())) for _ in range(N)] 활용
3. 모든 사람을 비교해 등수 정하기
   • 이중for문 활용
4. 등수 출력하기
   • print(*ranks)활용

 

📌 정답 코드(1회차)

import sys

# 1. 전체 사람의 수 N 입력받기
N = int(sys.stdin.readline())

# 2. 몸무게, 키(x, y) 입력받기
people = [tuple(map(int, input().split())) for _ in range(N)]

ranks = []
# 3. 모든 사람을 비교해 등수 정하기
for i in range(N):
    rank = 1 # 등수는 1부터 시작
    for j in range(N):
        if i != j:  # 자기 자신은 비교하지 않음
            if people[i][0] < people[j][0] and people[i][1] < people[j][1]:
                rank += 1
    ranks.append(rank)
# 4. 등수 출력하기
print(*ranks)