[2751] 수 정렬하기2

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

2751번: 수 정렬하기 2

 

 

엄청 빨리 끝날 줄 알고 호기롭게 가장 먼저 시작한 과제인데..............

merge sort가 아직 완벽하게 이해가 안되어있었기도 했고 노트북에 문제가 있어서 비쥬얼 스튜디오에서 실행창이 제대로 종료되지 않았다. 

그래서 혹시나 하고 그냥 코드만 복사해서 백준에 돌려봤더니 맞았습니다가 떴다 ㅋㅋㅋㅋㅋㅋㅋㅋ

얼른 학교에서 노트북 빌려줬으면 좋겠다.. 

 

 

💡 내 코드(C)

/*[2751] 수 정렬하기2*/
/*https://www.acmicpc.net/problem/2751*/

#include <stdio.h>
#define MAX 1000000
void mergesort(int num[], int left, int right);
void merge(int num[], int left, int mid, int right);
int n;
int num[MAX];

int main(void)
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
    	scanf("%d", &num[i]);
    }
        
    mergesort(num, 0, n - 1);
    
    for (int i = 0; i < n; i++) {
    	printf("%d\n", num[i]);
    }
}

void mergesort(int num[], int left, int right)
{
    int mid;
    
    // left==right, 즉 원소가 1개이면 종료
    if (right > left) {
        mid = (left + right) / 2; // 분할(divide)
        mergesort(num, left, mid); // 앞부분 리스트 정렬(conquer)
        mergesort(num, mid + 1, right); // 뒷부분 리스트 정렬(conquer)
        merge(num, left, mid + 1, right); // 정렬된 2개의 부분 배열 결합(combine)
    }
}

// 둘 중에 작은 값을 취해서 temp에 저장
void merge(int num[], int left, int mid, int right) 
{
    int left_end, num_elements, tmp_pos;
    int temp[MAX];
    left_end = mid - 1; // 왼쪽 segment중 가장 오른쪽 index
    tmp_pos = left;
    num_elements = right - left + 1; // 원소의 개수
    
    while ((left <= left_end) && mid <= right) {
        if (num[left] <= num[mid]) {
            temp[tmp_pos] = num[left];
            tmp_pos = tmp_pos + 1;
            left = left + 1;
        }
        else {
            temp[tmp_pos] = num[mid];
            tmp_pos = tmp_pos + 1;
            mid = mid + 1;
        }
    }
    
    // 첫 번째 segment에 남아있는 항목을 추가
    while (left <= left_end) {
        temp[tmp_pos] = num[left];
        left += 1;
        tmp_pos += 1;
    }
    
    while (mid <= right) {
        temp[tmp_pos] = num[mid];
        mid += 1;
        tmp_pos += 1;
    }
    
    // 임시 배열 temp의 값을 원래 배열 num에 복사
    for (int i = 0; i < num_elements; i++) {
        num[right] = temp[right];
        right -= 1;
    }
}