[Python] 백준 알고리즘 #7568 덩치

문제풀이

 

이번 문제도 위 '1436번 영화감독 숌' 문제와 같이 브루트 알고리즘을 사용하면 쉽게 풀리는 문제이다. 

 

키와 몸무게가 모두 자신보다 커야 자신보다 덩치가 크다는 조건이 있다. 

 

A부터 보았을 때, 다음 표를 보면 이해하기 쉽다.

	weight	height	A보다 덩치가 큰가?
A	55	185	같은 사람은 넘어감
B	58	183	x (A보다 덩치가 크지않음)
C	88	186	o (A보다 덩치가 큼)
D	60	175	x
E	46	155	x

A부터 나머지 전부 비교했을 때, 자신보다 덩치가 큰사람 횟수가 덩치 rank 인 것이다. A보다 덩치가 큰 사람은 B혼자 밖에 없으니 2등인 셈이다. 

 

A부터 ~ E까지 모두 나머지를 비교하였을 때, 2중 반복문으로 O(N^2) 의 시간복잡도에 해결 할 수있다.

 

 

소스코드

 

import sys
input = sys.stdin.readline

N = int(input())
students = []
for i in range(N):
    w, h = map(int, input().split())
    students.append([w,h])

rank = []
for i in range(N):
    counts = 1
    for j in range(N):
        if i==j:
            continue
        else:
            if students[i][0] < students[j][0] and students[i][1] < students[j][1]:
                counts+=1
    rank.append(counts)
print(" ".join(str(i) for i in rank))

 

 

www.acmicpc.net/problem/7568

7568번: 덩치