2019-05-01-[백준]-2751번

---

layout: post
title: "[백준] 2751번_수 정렬하기 2"
date: 2019-05-06
desc: "백준 2751번"
keywords: "Algorithm"
categories: [Algorithm]
tags: [백준, 알고리즘, 2751번, 수정렬하기2, c++]
icon: icon-html

---

백준_2751번

---

혼자 데이터 넣고 했을 때는 잘 정렬되는데 백준 사이트에서는 왜 틀렸다고 하는지… 생활관에서 다시 풀어봐야겠음…

수 정렬하기 2 (실패)

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

---

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

---

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

---

예제 입력 1

5
5
4
3
2
1

예제 출력 1

1
2
3
4
5

---

출처

• 데이터를 추가한 사람: ho94949

---

비슷한 문제

• 2750번. 수 정렬하기
• 10989번. 수 정렬하기 3

---

풀이

{: width="1024" height="512"}

---

---

소스코드

#include <iostream>

using namespace std;
void divide(int start, int end);
void mergeSort(int start, int end);

int *arr,*arr2;

int main()
{
    int n;
    cin >> n;

     arr=new int[n];
    arr2=new int[n];

    for(int i=0; i<n; i++) {
        cin >> arr[i];
    }

    divide(0, n-1);
    for(int i=0; i<n; i++){
        cout<<arr2[i]<<"\n";
    }
    return 0;
}

void divide(int start, int end) {
    int mid;

    if(start<end) {
        mid=(start+end)/2;
        divide(start,mid);
        divide(mid+1,end);
        mergeSort(start, end);
    }
}

void mergeSort(int start, int end) {
    int mid = (start+end)/2;

    int i=start;
    int j=mid+1;
    int k=start;

    while(i<=mid && j<=end){
        if(arr[i]<=arr[j]){
            arr2[k++]=arr[i++];
        }
        else{
            arr2[k++]=arr[j++];
        }
    }
    int temp;

    if(i>mid) {
        temp=j;
    }
    else{
        temp=i;
    }

    while(k<=end) {
        arr2[k++]=arr[temp++];
    }

    for(int i=start;i<=end; i++){
        arr[i]=arr2[i];
    }
}