[백준 11650] 좌표 정렬하기

1. 링크

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

2. 문제 설명

1) 문제

2차원 평면 위의 점 N개가 주어진다. 좌표를 x좌표가 증가하는 순으로, x좌표가 같으면 y좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오.

 

2) 입력

첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다.

 

3) 출력

첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력한다.

 

3. 코드

#11650

#입력받기
coordinates = []
for i in range(int(input())):
    x, y = map(int, input().split())
    coordinates.append([x, y])

#정렬해서 출력하기
coordinates.sort()
for j in coordinates:
    print(j[0], j[1])
    
#sorted()는 시간초과, .sort()는 통과

4. 설명

우선 주어진 입력들을 받는다. N은 곧바로 int(input())으로 받고, 먼저 선언한 coordinates 리스트에 주어진 좌표를 이중 리스트 형태로 append 해준다.

그 후 sort() 메서드를 적용한 후, 출력 포맷에 맞게 이중 리스트 안의 x, y 좌표를 0, 1 인덱스를 통해 출력하면 끝이다.

5. 배운 점

C++이나 Java 등 다른 언어였으면 분명 이것보다는 복잡하게 짰을텐데... 파이썬에서는 어이 없을 정도로 아무 생각 없이 써낸 코드가 통과를 받았다.

다만 첫 코드에서는 sort() 메서드 대신 sorted() 함수를 사용했는데, 이 때 시간초과가 발생하였다. 처음에는 sort()와 sorted()의 시간 복잡도가 달라서 그런 줄 알았는데, 이상하게 검색을 해봐도 둘다 Timsort 기반에 O(nlogn)이었다. 좀 더 서치해보고 보충해야겠다:(