백준 7568번 덩치 파이썬

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

7568번: 덩치

 

내 코드

big = []
result = []
N = int(input())

for i in range(N):
    x, y = list(map(int, input().split()))
    big.append((x, y))
    
for i in range(N):
    cnt = 1
    for j in range(N):
        if big[i][0] < big[j][0] and big[i][1] < big[j][1]:
            cnt += 1
    result.append(cnt)

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

'''
for i in range(N):
    print(result[i], end = " ")
로 출력 해도 됩니다.
'''

---

Review

 

주어진 조건에 의하면 O(N²) 으로 충분히 풀 수 있는 조건 이기 때문에,
많은 생각하지 않고 2중 for 문으로 풀었습니다.

시간 복잡도를 줄이고 싶었지만, 모든 경우를 다 살펴봐야 등수를 매길 수 있습니다.

따라서 시간 복잡도는 O(N²)입니다.

 

다른 풀이 방법이 있다면 댓글로 공유 부탁드립니다.
( ̳• ·̫ • ̳)

질문이나 지적할 사항 있으면 언제든지 의견 주세요
（ •́ .̫ •̀ ）