-
[백준 7568번] 덩치Coding Test/백준 2021. 3. 19. 03:16
# 문제
내 풀이
n = int(input()) # 사람들의 덩치 정보 입력 받기 people = [tuple(map(int, input().split())) for _ in range(n)] # 현재 사람의 덩치를 다른 모든 사람들과 비교하여 for i in range(n): rank = 1 # 만일 현재 사람보다 덩치가 큰 사람이 있다면, rank를 1 증가시킴 for j in range(n): if people[i][0] < people[j][0] and people[i][1] < people[j][1]: rank += 1 # 현재 사람의 등수 출력 print(rank, end=' ')
생각해볼 점
처음엔 입력 수가 많지 않아 조건에 맞춰 bubble sort를 한 후, 정렬된 정보대로 차례차례 비교하며 등수를 출력해보면 어떨까 했다. 그런데 무언가 깔끔한 느낌이 없는 것 같아 다른 풀이를 찾아보니, 굳이 정렬할 필요없이 완전탐색으로 전부 비교하며 접근하는 것이 현명했던 것 같다.
시간 복잡도
O(N²) - n이 최대 50이라 큰 문제 없었음
'Coding Test > 백준' 카테고리의 다른 글
[백준 1644번] 소수의 연속합 (0) 2021.03.22 [백준 1436번] 영화감독 숌 (0) 2021.03.19 [백준 1806번] 부분합 (0) 2021.03.16 [백준 2470번] 두 용액 (0) 2021.03.13 [백준 3273] 두 수의 합 (0) 2021.03.10