[Python] 백준 7568번: 덩치 - brute force

문제

7568번: 덩치

풀이

완전탐색 (브루트포스)를 통해서 풀 수 있다. 

처음엔 정렬을 해서(reversed) 바로 위에 애랑만 비교하는 방식으로 짰는데, 그럴 경우 반례가 생긴다. 

 

input

5
177 75
133 16
183 75
126 156
49 24

output

1 3 1 3 5

 

answer

1 3 1 1 4

 

 

따라서 머리쓰지 않고 문제에서 시키는대로 짰다. 

만일 자신보다 더 큰 덩치의 사람이 k명이라면 그 사람의 덩치 등수는 k+1이 된다

따라서 각각의 사람마다 자신보다 더 큰 덩치의 사람이 몇명인지 완전탐색으로 세줬고, 거기에 1을 더해 등수를 정해줬다.

 

주어진 숫자의 범위가 작은 문제는 겁먹지말고 그냥 완전탐색으로 빨리 돌리자는 교훈을 얻었다

import sys

# N: 사람 수
N = int(sys.stdin.readline())
people = []

# 인풋 받기
for i in range(N):
    x, y = map(int, sys.stdin.readline().split(" "))
    people.append([x, y, 0])

# 만일 자신보다 더 큰 덩치의 사람이 k명이라면 그 사람의 덩치 등수는 k+1이 된다 -> 본인보다 덩치 큰 사람 세기
for i in range(len(people)):
    k = 0
    for j in range(len(people)):
        if i != j:
            if people[i][0] < people[j][0] and people[i][1] < people[j][1]:
                k += 1

    # k에 1 더해서 등수에 저장 
    people[i][2] = k + 1


# 출력
for each in people:
    print(each[2], end=" ")