백준 11004번: K번째 수 - 정렬 Sort(), Quick Sort, Insertion Sort

 

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

 

문제요약

A를 오름차순 정렬했을 때, 앞에서부터 K번째 있는 수를 구하는 프로그램

 

난이도

Silver 5

---

풀이 포인트

• 시간초과 날 때 입출력 시간 단축 항상 생각하기!

ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);

• 정렬의 다양한 방법
  • Quick Sort
  • Insertion Sort

---

REVIEW

입출력단축을 생각하지 못하고, Sort()내장함수를 썼는데 시간초과가 나서

시간복잡도가 더 낮은 정렬을 구현해야 한다고 생각했다.

 

<algorithm>라이브러리에 내장된 Sort함수는 정렬 중에서도 시간복잡도가 낮은 편에 속하는 Quick Sort를 기반으로 구현되어 있다고 하니, 특별한 조건대로 정렬을 하는 것이 아닌 단순한 오름, 내림 차순이라면 내장함수를 쓰는 것이 효과적일듯 하다!

 

그래도 공부하는 김에 삽입 정렬과 퀵 정렬 2가지 정도 더 구현해보았다.

---

CODE

 

방법1 : Sort() 내장 함수 활용

#include <iostream>
#include <algorithm>
using namespace std;

int n, k, a;
vector<int> v;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n >> k;
    
    for(int i = 0 ; i < n; i++){
        cin >> a;
        v.push_back(a);
    }

    // 방법 1: Sort
    sort(v.begin(), v.end());

    cout << v[k-1] << endl;    
}

 

방법2 : Insertion Sort & Quick Sort - 둘 다 시간초과

#include <iostream>
#include <algorithm>
using namespace std;

int n, k, a;
vector<int> v;

void insertionSort(vector<int> v){
    int key, i, j;

    for(i= 1; i < v.size(); i++){
        key = v[i];
        for(j = i - 1; j >= 0 && v[j] > key; j--){
            v[j + 1] = v[j];
        }
        v[j+1] = key;
    }
}

void quickSort(vector<int>& data, int start, int end) {  // 참조로 전달
    if (start >= end) return;
    
    int pivot = start;
    int i = start + 1;
    int j = end;

    while (i <= j) {
        while (i <= end && data[i] <= data[pivot]) i++;
        while (j > start && data[j] >= data[pivot]) j--;

        if (i > j) {
            swap(data[j], data[pivot]);
        } else {
            swap(data[i], data[j]);
        }
    }

    quickSort(data, start, j - 1);
    quickSort(data, j + 1, end);
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n >> k;
    
    for(int i = 0 ; i < n; i++){
        cin >> a;
        v.push_back(a);
    }

    // 방법 1: Sort
    //sort(v.begin(), v.end());

    // 방법 2: Insertion Sort : 시간 초과
    //insertionSort(v);

    // 방법 3: Quick Sort
    quickSort(v, 0, v.size() - 1);

    cout << v[k-1] << endl;    
}