[class2]백준 11650번(좌표 정렬하기) - 코테공부 24일차(2025.02.15)

문제유형

정렬 알고리즘

풀이 방법 도출 과정

1. 정렬 알고리즘에 key 매개변수를 활용하도록 하겠다. 

시간 복잡도

입력은 각각 100,000개 가능 정렬 알고리즘은 NlogN이기 때문에 100000 x log100000(17) = 170만번정도 1억번에는 미치지 않는다. 이것이 2번을 하고 있기 때문에 340만번이다. 시간복잡도는 O(NlogN)정도로 생각하면 된다. 

코드 및 간단설명

매개 변수 key값을 사용해보았다.

N = int(input())
lst = [list(map(int, input().split())) for _ in range(N)]

# 첫 번째 요소(lst[0])를 기준으로 정렬하고, 첫 번째 요소가 같다면 두 번째 요소(lst[1])로 정렬
sorted_lst = sorted(lst, key=lambda x: (x[0], x[1]))

# 출력
for item in sorted_lst:
    print(*item)

 

다른 풀이

1) 파이썬 라이브러리 사용

아래는 operator.itemgetter를 사용하여 in-place 정렬하는 방법이다.
itemgetter는 C로 구현되어 있어 lambda보다 약간 더 빠른 성능을 보일 수 있다.

from operator import itemgetter

N = int(input())
lst = [list(map(int, input().split())) for _ in range(N)]

# in-place 정렬: 첫 번째 요소, 그 다음 두 번째 요소 기준으로 정렬
lst.sort(key=itemgetter(0, 1))

for item in lst:
    print(*item)