2023-08-13-sort-inside-1427

• toc {:toc}

문제 확인하기

풀이

1. sort 함수를 이용하여 풀이 sort 함수는 기본적으로 오름차순으로 설정되어 있기 때문에 내림차순으로 정렬하기 위해선 greater<>() 를 넣어줘야 한다. 본래 <> 안에 자료형을 명시해줘야 하나, C++14 부터는 명시해주지 않아도 사용할 수 있다.

2. Quick Sort 를 구현하여 풀이

• Quick sort 과정.
  • pivot 을 잡는다. (시작, 중간, 끝 등 많은 방식이 있다. 나는 시작값으로 잡았다.)
  • left = i 는 맨 왼쪽, right = j 는 맨 오른쪽에서 출발한다.
  • left 의 경우 pivot 보다 큰 경우를 찾는다. 끝에 도달할 때까지 찾는다.
  • right 의 경우 pivot 보다 작은 경우를 찾는다. 끝에 도달할 때까지 찾는다.
  • 만약 left 와 right 가 서로 엇갈린 경우 pivot 과 right 를 바꿔준다. 이렇게 되면 pivot 의 왼쪽에는 pivot 보다 큰 값만 남게 된다.
  • 엇갈리지 않고 left 와 right 가 결정된 경우 두 값을 바꿔준다.

#include <bits/stdc++.h>
using namespace std;
 
int num[11];
 
void quick_sort(int *data, int start, int end){
    if(start >= end){
        // 원소가 1개인 경우
        return; 
    }
    
    int pivot = start;
    int i = pivot + 1; // 왼쪽 출발 지점 
    int j = end; // 오른쪽 출발 지점
    int temp;
    
    while(i <= j){
        // 포인터가 엇갈릴때까지 반복
        while(i <= end && data[i] >= data[pivot]){
            i++;
        }
        while(j > start && data[j] <= data[pivot]){
            j--;
        }
        
        if(i > j){
            // 엇갈림
            temp = data[j];
            data[j] = data[pivot];
            data[pivot] = temp;
        }else{
            // i번째와 j번째를 스왑
            temp = data[i];
            data[i] = data[j];
            data[j] = temp;
        }
    } 
    
    // 분할 계산
    quick_sort(data, start, j - 1);
    quick_sort(data, j + 1, end);
}
 
// quick sort 구현해서 풀이
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    int N, idx = 0, k;
    cin >> N;
    while(true){
        k = N % 10;
        num[idx++] = k;
        N = N/10;
        if(N == 0) break;
    }
 
    quick_sort(num, 0, idx-1);
 
    for(int i = 0; i<idx; i++){
        cout << num[i];
    }
 
    return 0;
}
 
// sort 함수 사용하여 풀이
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    string N;
    cin >> N;
    sort(N.begin(), N.end(), greater<>());
    cout << N << '\n';
 
    return 0;
}