2750번: 수정렬하기2

문제 보기

2751번: 수 정렬하기 2

 

나의 풀이 - 병합정렬 O(nlogn)

# 정렬이 된 두 배열을 합치면서 정렬시키는 함수
def merge(array1, array2):
    result = []
    array1_index = 0
    array2_index = 0
    while array1_index < len(array1) and array2_index < len(array2):
        if array1[array1_index] < array2[array2_index]:
            result.append(array1[array1_index])
            array1_index += 1
        else:
            result.append(array2[array2_index])
            array2_index += 1

    # 남아있는 값들 전부 추가. 인덱스가 해당 배열을 모두 확인했다면, 다른 배열은 원소가 남아있다.
    if array1_index == len(array1):
        result += array2[array2_index:]

    if array2_index == len(array2):
        result += array1[array1_index:]

    return result

# 큰 하나의 문제를 작은 문제로 쪼개어 푸는 방식으로 배열을 재귀적으로 쪼개주는 함수
# 그와 동시에 가장 작은 단위인 1개로 쪼개어지고 그 두배열을 합쳐서 다시 올라가는 식으로 배열을 정렬함.
def sorted_merge(arr):
    # 재귀 탈출 조건
    if len(arr) == 1:
        return arr
    
    # 재귀적으로 배열을 1개로 쪼개는 작업
    arr1, arr2 = sorted_merge(arr[len(arr)//2:]), sorted_merge(arr[:len(arr)//2])

    # 해당 배열들을 순서대로 정렬
    return merge(arr1, arr2)

n = int(input())
arr = [int(input()) for _ in range(n)]

for i in sorted_merge(arr):
    print(i)

sort함수는 병합정렬이란 알고리즘으로 구현이 되어있고 이를 코드로 구현해보는 문제이다.

1) 정렬 된 두 배열을 받아 각 인덱스의 값에 따라 정렬해주는 함수를 생성

[1, 2, 3, 5]  # 정렬된 배열 A
[4, 6, 7, 8]  # 정렬된 배열 B
[] # 두 집합을 합칠 빈 배열 C

        ↓
1단계 : [**1**, 2, 3, 5] 
        ↓
       [**4**, 6, 7, 8] 
        1과 4를 비교합니다!
        1 < 4 이므로 1을 C 에 넣습니다.
     C:[1]

           ↓
2단계 : [1, **2**, 3, 5] 
        ↓
       [**4**, 6, 7, 8] 
        2와 4를 비교합니다!
        2 < 4 이므로 2를 C 에 넣습니다.
     C:[1, 2]

              ↓
3단계 : [1, 2, **3**, 5] 
        ↓
       [**4**, 6, 7, 8] 
        3과 4를 비교합니다!
        3 < 4 이므로 3을 C 에 넣습니다.
     C:[1, 2, 3]

                 ↓
3단계 : [1, 2, 3, **5**] 
        ↓
       [**4**, 6, 7, 8] 
        5와 4를 비교합니다!
        5 > 4 이므로 4을 C 에 넣습니다.
     C:[1, 2, 3, 4]

                 ↓
3단계 : [1, 2, 3, **5**] 
           ↓
       [4, **6**, 7, 8] 
        5와 6을 비교합니다!
        5 < 6 이므로 5을 C 에 넣습니다.
     C:[1, 2, 3, 4, 5]

엇, 이렇게 되면 A 의 모든 원소는 끝났습니다!

그러면 B에서 안 들어간 원소인
       [6, 7, 8] 은 어떡할까요?
하나씩 C 에 추가해주면 됩니다.
     C:[1, 2, 3, 4, 5, 6, 7, 8] 이렇게요!

그러면 A 와 B를 합치면서 정렬할 수 있었습니다.

한 번, 직접 이 로직을 코드로 구현해보겠습니다!

 

2) 재귀함수를 통해 배열을 1개로 쪼개어 머지함수에 매개변수로 넣고 반환 

 

 ✅ 분할 정복의 개념을 적용

분할 정복은 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략입니다.

예를 들어서 [5, 4] 라는 배열이 있다면 이 배열을 [5] 와 [4] 를 가진 각각의 배열로 작은 2개의 문제로 분리해서 생각하는 것입니다. 그러면 이 둘을 합치면서 정렬한다면? 결국 전체의 정렬된 리스트가 될 수 있습니다.

이 개념을 조금 더 확대해서 생각해보겠습니다.

[5, 3, 2, 1, 6, 8, 7, 4] 이라는 배열이 있다고 하겠습니다. 이 배열을 반으로 쪼개면 [5, 3, 2, 1] [6, 8, 7, 4] 이 됩니다. 또 반으로 쪼개면 [5, 3] [2, 1] [6, 8] [7, 4] 이 됩니다. 또 반으로 쪼개면 [5] [3] [2] [1] [6] [8] [7] [4] 이 됩니다.

이 배열들을 두개씩 병합을 하면 어떻게 될까요? [5] [3] 을 병합하면 [3, 5] 로 [2] [1] 을 병합하면 [1, 2] 로 [6] [8] 을 병합하면 [6, 8] 로 [7] [4] 을 병합하면 [4, 7] 로 그러면 다시! [3, 5] 과 [1, 2]을 병합하면 [1, 2, 3, 5] 로 [6, 8] 와 [4, 7]을 병합하면 [4, 6, 7, 8] 로 그러면 다시! [1, 2, 3, 5] 과 [4, 6, 7, 8] 를 병합하면 [1, 2, 3, 4, 5, 6, 7, 8] 이 됩니다.

어떤가요? 문제를 쪼개서 일부분들을 해결하다보니, 어느새 전체가 해결되었습니다! 이를 분할 정복, Divide and Conquer 라고 합니다.