[백준] 11650: 좌표 정렬하기 / 파이썬 / 정렬 / Sorting

💻 문제

정렬에 해당하는 백준 11650: 좌표 정렬하기 문제이다.

---

💡 코드

초기 코드

import sys

N = int(input())
const = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

for i in range(N):
    for j in range(N-i-1):
        if const[j][0] > const[j+1][0] or (const[j][0]==const[j+1][0] and const[j][1]>const[j+1][1]):
            const[j], const[j+1] = const [j+1], const [j]

for point in const:
    print(point[0], point[1])

문제를 딱 보자마자 생각나는대로 bubble sort를 사용하여 풀었더니 당연한 결과이겠지만 시간 초과가 떴다.
❗️ bubble sort의 시간복잡도는 O(n^2) 로 최악이니 절대 사용하지 말자..

그래서 해결책으로 파이썬 내장함수인 sort 함수를 사용하였다. 이 함수는 O(nlogn)의 시간복잡도를 가진다.

정답 코드

import sys
N = int(input())
const = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
const_s = sorted(const)

for point in const_s:
    print(point[0], point[1])

sorted 함수를 사용하면 오름차순으로 저절로 해주니 얼마나 편한지..!!

---

💪🏻 TIL

• map() : 입력된 값을 특정 값으로 반환해줌

• split() : 분할 값을 기준으로 입력된 값을 나눔

+) 파이썬 sort/ sorted 정리글

시간 복잡도를 생각하려해도 잘 생각나지 않는걸 보니 자료구조 복습이 절실히 필요하다고 느낀다 😭
또 파이썬 내장 함수를 그냥 사용하는게 아니라 각 함수가 어떤 시간 복잡도를 가지는지 공부하는 시간을 가져야겠다.