Search

BOJ 11650 좌표 정렬하기

태그
정렬
URL
한 줄 요약 시간 제한 조건에 있어 아슬아슬한 경우에는 정확한 연산 횟수를 구할 필요가 있으나, 시간 제한에 있어 넉넉하다는 것이 자명하면 대략적인 시간 복잡도를 구하면 된다.
www.acmicpc.net
https://www.acmicpc.net/problem/11650

문제 설명

•
NN개의 점 (x,y)(x, y)가 주어지면, xx에 대해 오름차순으로 정렬, xx가 같으면 yy에 대해 오름차순으로 정렬하는 문제
•
입력으로 위치가 같은 두 점은 주어지지 않는다.

예제 입력/출력

•
입력1
5 3 4 1 1 1 -1 2 2 3 3
Plain Text
복사
•
출력1
1 -1 1 1 2 2 3 3 3 4
Plain Text
복사

제약 조건

•
1≤n≤100,0001 ≤ n ≤ 100,000
•
−100,000≤xi,yi≤100,000-100,000 ≤ x_i, y_i ≤ 100,000

문제 풀이

•
파이썬의 정렬 함수를 이용하면 된다.
◦
sorted() → 병합 정렬 N⋅log2NN \cdot log_2N

시간 복잡도 계산

•
최악의 경우 340만회
◦
(x,y)−(x,y)(x, y) - (x, y) 비교 시, 최악의 경우 최대 2회 비교
◦
=2⋅(100,000⋅log2(100,000))= 2 \cdot (100,000 \cdot log_2(100,000))
▪
log2(100,000)=217log_2(100,000) = 2^{17}

풀이 코드

N = int(input()) dots = [list(map(int, input().split())) for _ in range(N)] dots = sorted(dots) for x, y in dots: print(x, y)
Python
복사

알아두면 좋은 내용들

시간 복잡도를 계산할 때는 얼마나 정확하게 계산해야 할까?