[백준] 11650번 좌표 정렬하기 파이썬

첫줄 : 입력할 점의 개수 N

N줄 : 점( x와 y 값 )

입력받은 점을 x부터 정렬, x가 같으면 y에 따라 정렬

 

2845번 파티가 끝나고 난 뒤 풀이

 

[시도1] pypy3 시간 초과

n = int(input())
numbers = []

for i in range(0, n):
  a, b = map(int, input().split())
  numbers.append([a,b])
  numbers.sort()

for i in range(0, n):
  num = numbers[i]
  a = num[0]
  b = num[1]
  print(str(a) + ' ' + str(b))

 

[시도2] pypy3 시간 초과

import sys

n = int(sys.stdin.readline())
numbers = []

for i in range(0, n):
  a, b = map(int, sys.stdin.readline().split())
  numbers.append([a,b])
  numbers.sort()

for i in range(0, n):
  num = numbers[i]
  a = num[0]
  b = num[1]
  print(str(a) + ' ' + str(b))

입력방식을 input()에서 sys.stdin.readline()으로 바꾸어 시간을 단축해보려고 했으나 바꾼 코드도 시간초과가 났다.

 

[시도3] pypy3 맞았습니다!

import sys

n = int(sys.stdin.readline())
numbers = []

for i in range(0, n):
  a, b = map(int, sys.stdin.readline().split())
  numbers.append([a,b])
  
numbers.sort()

for i in range(0, n):
  num = numbers[i]
  print(str(num[0]) + ' ' + str(num[1]))

sotr()를 for문 밖에서 해주어서 복잡도를 낮춰주었다.

주변 알고리즘 고수에게 물어봤더니 [시도2]는 for문 안에 정렬을 하므로 N^2logN의 복잡도를 가지고, [시도3]처럼 for문 이후에 정렬을 하게되면 NlogN의 복잡도를 가진다고 한다.

 

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

11650번: 좌표 정렬하기