[백준] 11651번 좌표 정렬하기 2 해설 및 풀이 (Python)

백준 11651번 좌표 정렬하기 2

 

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

 

---

문제

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

입력

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

출력

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

---

문제 유형

​정렬

 

풀이 방법 도출

 

1. 첫 번째 줄에서 점의 개수 N을 입력 받습니다.
2. 이후 N개의 점 좌표 (x,yx, yx,y)를 리스트에 저장합니다.
3. 점을 정렬할 때 y좌표를 우선적으로 오름차순으로 정렬합니다.
4. 만약 y좌표가 같은 경우 x좌표를 기준으로 오름차순 정렬합니다.
5. 정렬된 점을 순서대로 출력합니다.

---

핵심 코드 삽입 및 설명

 

sort 라이브러리 사용

import sys

# 빠른 입력 사용
input = sys.stdin.readline

# 점의 개수 입력
N = int(input())

# N개의 점만큼 입력받아 리스트에 저장
points = [list(map(int, input().split())) for _ in range(N)]

# y좌표 오름차순 정렬 후 y좌표가 같다면 x좌표 오름차순 정렬
points.sort(key=lambda x: (x[1], x[0]))

# 정렬된 점을 출력
for point in points:
    print(point[0], point[1])

 

시간 복잡도

• 시간 복잡도는 O(N log⁡ N)

 

-> 백준에 제출 시, 컴파일 에러가 난다.

 

sort 라이브러리를 사용하지 않고 "병합 정렬"을 사용해서 작성한 코드

import sys

input = sys.stdin.readline

# 점의 개수 입력
N = int(input())

# 점의 리스트 입력받기
points = [list(map(int, input().split())) for _ in range(N)]

# 병합 정렬 구현
def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    # 배열을 절반으로 나누기
    mid = len(arr) // 2
    left_half = merge_sort(arr[:mid])
    right_half = merge_sort(arr[mid:])

    # 병합 과정
    merged = []
    i = j = 0

    while i < len(left_half) and j < len(right_half):
        # 정렬 기준: y값이 작은 순
				# 같다면 x값이 작은 순
        if left_half[i][1] < right_half[j][1] or (left_half[i][1] == right_half[j][1] and left_half[i][0] < right_half[j][0]):
            merged.append(left_half[i])
            i += 1
        else:
            merged.append(right_half[j])
            j += 1

    # 남은 요소 추가
    while i < len(left_half):
        merged.append(left_half[i])
        i += 1

    while j < len(right_half):
        merged.append(right_half[j])
        j += 1

    return merged

# 정렬 실행
sorted_points = merge_sort(points)


# 정렬된 결과 출력
for point in sorted_points:
    print(point[0], point[1])

 

시간복잡도

• 병합 정렬의 시간 복잡도는 O(N log⁡ N)

 

sort 라이브러리를 사용하지 않고 "선택 정렬"을 사용해서 작성한 코드

import sys

input = sys.stdin.readline

# 점의 개수 입력
N = int(input())

# 점의 리스트 입력받기
points = [list(map(int, input().split())) for _ in range(N)]

# 선택 정렬 구현
def selection_sort(arr):
    n = len(arr)
    
    for i in range(n - 1):
        min_idx = i
        for j in range(i + 1, n):
            # 정렬 기준: y값이 작은 순
            # 같다면 x값이 작은 순
            if arr[j][1] < arr[min_idx][1] or (arr[j][1] == arr[min_idx][1] and arr[j][0] < arr[min_idx][0]):
                min_idx = j
        
        # 최소값과 현재 위치 교환
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

# 정렬 실행
selection_sort(points)

# 정렬된 결과 출력
for point in points:
    print(point[0], point[1])

 

시간 복잡도

• 선택 정렬은 O(N^2)