한 줄 요약
시간 제한 조건에 있어 아슬아슬한 경우에는 정확한 연산 횟수를 구할 필요가 있으나,
시간 제한에 있어 넉넉하다는 것이 자명하면 대략적인 시간 복잡도를 구하면 된다.
문제 설명
•
개의 점 가 주어지면, 에 대해 오름차순으로 정렬, 가 같으면 에 대해 오름차순으로 정렬하는 문제
•
입력으로 위치가 같은 두 점은 주어지지 않는다.
예제 입력/출력
•
입력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
복사
제약 조건
•
•
문제 풀이
•
파이썬의 정렬 함수를 이용하면 된다.
◦
sorted() → 병합 정렬
시간 복잡도 계산
•
최악의 경우 340만회
◦
비교 시, 최악의 경우 최대 2회 비교
◦
▪
풀이 코드
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
복사
알아두면 좋은 내용들
시간 복잡도를 계산할 때는 얼마나 정확하게 계산해야 할까?