백준 22.01.27. 11650번 - 좌표 정렬하기

---

틀린코드

N = int(input())

loc = []

for _ in range(N):
    x, y = map(int, input().split())
    loc.append([x, y])

for i in range(len(loc)):
    for j in range(len(loc)):
        if loc[i][0] < loc[j][0]:
            loc[i], loc[j] = loc[j], loc[i]
        elif loc[i][0] == loc[j][0]:
            if loc[i][1] < loc[j][1]:
                loc[i], loc[j] = loc[j], loc[i]

for _ in range(len(loc)):
    print(loc[_][0], loc[_][1])

버블정렬로 구현했습니다.

결괏값은 올바르게 나오지만 시간초과가 나온 것으로 보아 아무래도 시간적인 측면에서 올바른 알고리즘이 아닌듯 합니다.

 

def mergeSort(arr):
    if len(arr) < 2:
        return arr

    mid = len(arr) // 2
    arr1 = mergeSort(arr[:mid])
    arr2 = mergeSort(arr[mid:])

    i = j = 0
    mergedList = []

    while i < len(arr1) and j < len(arr2):
        if arr1[i][0] < arr2[j][0]:
            mergedList.append(arr1[i])
            i += 1
        elif arr[i][0] == arr2[j][0]:
            if arr[i][1] < arr2[j][1]:
                mergedList.append(arr[i])
                i += 1
            else:
                mergedList.append(arr[j])
                j += 1
        else:
            mergedList.append(arr2[j])
            j += 1

    mergedList += arr1[i:]
    mergedList += arr2[j:]
    return mergedList


N = int(input())

loc = []

for _ in range(N):
    x, y = map(int, input().split())
    loc.append([x, y])

loc = mergeSort(loc)

for _ in range(len(loc)):
    print(loc[_][0], loc[_][1])

합병정렬로도 구현해보았습니다.

하지만 코드가 틀렸는지 틀렸습니다!가 떴습니다.

---

N = int(input())

loc = []

for _ in range(N):
    x, y = map(int, input().split())
    loc.append([x, y])

loc.sort()

for _ in range(len(loc)):
    print(loc[_][0], loc[_][1])

 

간단하게 메서드 sort()를 사용하여 해결할 수 있는 문제입니다.