[GDSC Week1-3] 백준 11582번:: 치킨 TOP N (C++)

 

 

* 생각한 아이디어 및 문제 풀이

문제 자체가 merge 정렬의 과정이라고 생각했다.

merge 정렬을 하는 과정에서 마지막으로 합치는 과정을 생략하고 출력하면 되겠다고 생각했다.

 

 

* 코드

#include <iostream>
using namespace std;
#define MAX_SIZE 1048576
int sorted[MAX_SIZE];
int n, person;

void merge(int list[], int left, int mid, int right){
    if( (right-left) > (n/person) ) return;
    
    int i, j, k;
    i = left;
    j = mid+1;
    k = 0;
    
    /* 분할 정렬된 list의 합병 */
    while(i<=mid && j<=right){
        if(list[i]<=list[j])
          sorted[k++] = list[i++];
        else
          sorted[k++] = list[j++];
    }
    
    // 남아 있는 값들을 일괄 복사
    while(i <= mid){ 
        sorted[k++] = list[i++];
    }
    // 남아 있는 값들을 일괄 복사
    while (j <= right) {
        sorted[k++] = list[j++];
    }
    // 배열 sorted[](임시 배열)의 리스트를 배열 list[]로 재복사
    for(int l=left; l<=right; l++){
        list[l] = sorted[l-left];
    }
}

void merge_sort(int list[], int left, int right){
    if(left == right) return;
    int mid = (left+right)/2; 
    merge_sort(list, left, mid); // 앞쪽 부분 리스트 정렬 -정복(Conquer)
    merge_sort(list, mid+1, right); // 뒤쪽 부분 리스트 정렬 -정복(Conquer)
    merge(list, left, mid, right); // 정렬된 2개의 부분 배열을 합병하는 과정 -결합(Combine)
}

int main(){
    ios::sync_with_stdio(false); 
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n;
    int list[n];
    for(int i=0; i<n; i++){
      cin >> list[i];
    }
    cin >> person;
    
    // 합병 정렬 수행(left: 배열의 시작 = 0, right: 배열의 끝 = 7)
    merge_sort(list, 0, n-1);
    
    // 정렬 결과 출력
    for(int i=0; i<n; i++){
        cout << list[i] << ' ';
    }
}

 

 

* 문제 링크 :  https://www.acmicpc.net/problem/11582

11582번: 치킨 TOP N

 

 

* 회고

merge sort가 익숙하지 않아 코드 자체는 이해를 했지만

직접 코드에 적용하는 것에 어려움을 겪었다.

앞으로도 이런 알고리즘을 직접 구현해보는 코드를 많이 작성해보아야 겠다.