파이썬 Python | 알고리즘 | 백준 덩치

⭕ 파이썬 Python | 알고리즘 | 백준 덩치

➡️ 문제링크

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

 

➡️ 문제 탐색하기

• 두 사람 A와 B의 덩치가 각각 (x, y), (p, q) 일 때, x > p 그리고 y > q이라면 우리는 A의 덩치가 B의 덩치보다 "더 크다"라고 판단한다. 같은 방식으로 다른 사람들과 비교하여 자신의 덩치가 몇 번째인지 등수를 매긴다.
• 최대 N이 50이므로 O(N^2) 복잡도, 연산 약 2,500개로 시간복잡도 1초 안에 충분히 해결 가능하다. 입력 범위를 항상 잘 살피자! 이렇게 모든 경우의 수를 탐색해보는 알고리즘을 완전탐색 또는 브루트포스라고 한다.

 

➡️ 코드 설계하기

• 사람의 수 N과 각 사람의 몸무게와 키를 입력받는다.
• 각 사람의 몸무게와 키를 리스트에 저장한다.
• 각 사람의 초기 등수를 1로 설정한다.
• 이중 반복문을 사용하여 각 사람마다 다른 모든 사람과 덩치를 비교한다.  
  • 한 사람에 대해, 0부터 N-1까지의 각각의 사람에 대해 자신과 덩치를 비교한다. 0 ~ N-1까지의 사람들과 비교할 때 자기 자신과 비교하는 경우라면 비교를 넘어간다.

 

➡️ 시도 회차 수정 사항 (Optional)

1회차

• 런타임 에러 발생
• ranks 리스트를 제대로 초기화하지 않아서 발생했다.

import sys

N = int(sys.stdin.readline().strip())
arr = []

for i in range(N):
    weight, height = map(int, sys.stdin.readline().strip().split())
    arr.append((weight, height))

ranks = [1]  # 이 부분이 잘못됨, 모든 요소를 초기화해야 함

for i in range(N):
    for j in range(N):
        if i != j:
            if arr[j][0] > arr[i][0] and arr[j][1] > arr[i][1]:
                ranks[i] += 1  # IndexError 발생

print(" ".join(map(str, ranks)))

---

2회 차

• 시간 116ms
• ranks 리스트를 [1] * N으로 초기화하여 모든 요소를 1로 설정하였다.

import sys

N = int(sys.stdin.readline().strip())
arr = []

for i in range(N):
    weight, height = map(int, sys.stdin.readline().strip().split())
    arr.append((weight, height))

ranks = [1] * N  # 각 사람의 초기 등수를 1로 초기화

for i in range(N):
    for j in range(N):
        if i != j:
            if arr[j][0] > arr[i][0] and arr[j][1] > arr[i][1]:
                ranks[i] += 1

print(" ".join(map(str, ranks)))

 

➡️ 정답 코드

import sys

N = int(sys.stdin.readline().strip())
arr = []

for i in range(N):
    weight, height = map(int, sys.stdin.readline().strip().split())
    arr.append((weight, height))

ranks = [1] * N  # 각 사람의 초기 등수를 1로 초기화

for i in range(N):
    for j in range(N):
        if i != j:
            if arr[j][0] > arr[i][0] and arr[j][1] > arr[i][1]:
                ranks[i] += 1

print(" ".join(map(str, ranks)))