[실버5]백준 7568번(덩치) - 코테공부 42일차(2025.03.11)

문제유형

브루트 포스 알고리즘

풀이 방법 도출 과정

1. 몸무게가 x 키가 y라고 하면 (x,y)가 있는데 몸집을 대고 등수를 구하는 문제

2. 하지만 x보다 크고 y보다 크면 몸집이 크다고 할 수 있음, 하지만 x보다 크지만 y보다는 작으면 그건 몸집이 크다고 할 수 없음 그 반대도 마찬가지임. 

3. 이를 구현하고자 하는데 브루트포스적으로 풀어보도록 하겠다.

시간 복잡도

시간 복잡도는 a와 b를 구분하기 위해 for문을 중첩으로 쓰였기 때문에 O(N^2)이다. 그러나 N이 최악의 경우 50을 넘지 않기 때문에 시간복잡도에서 아무런 문제가 없다. 

코드 및 간단설명

브루트 포스 알고리즘을 사용하여 풀었다. 

N = int(input())  # 사람 수 입력
people = [list(map(int, input().split())) for _ in range(N)]  # 몸무게와 키 입력

ranks = []  # 덩치 등수를 저장할 리스트

for i in range(N):
    rank = 1  # 기본 등수는 1등
    for j in range(N):
        if i != j:  # 자기 자신과 비교할 필요 없음
            if people[j][0] > people[i][0] and people[j][1] > people[i][1]:  
                # 몸무게 & 키 모두 크면 등수 증가
                rank += 1  
    ranks.append(str(rank))  # 등수를 문자열로 저장 (공백으로 출력하기 위함)

print(" ".join(ranks))  # 등수를 공백으로 구분하여 출력