[BOJ/C++] 2751::수 정렬하기2 (정렬)

수 정렬하기 2

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	256 MB	291040	87375	60932	31.033%

 

문제

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

 

---

후기

 

처음에 "중복된 값은 없다."를 "중복된 값을 없애야한다."로 잘 못 읽어 set와 unique함수를 통한 중복 값 제거를 하려 했다.

뻘짓이었지만 문제 하나로 여러 실험을 해보게 되었다.

 

확실히 자료구조에 따라 속도와 공간 사용량의 차이가 극명해서 재미있었던 문제였다.

 

Array >> vector >>>>> set

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>

using namespace std;



// 	5812KH	676ms
void UsingSortOnArray(){
    int loop = 0;
    cin >> loop;

    int storage[loop];

    for (int k = 0; k < loop; k++) {
        cin >> storage[k];
    }

    sort(storage, storage + loop);

    for (int k = 0; k < loop; k++) {
        cout << storage[k] << '\n';
    }
}

// 8184KB	680ms
void UsingSortWithoutUnique(){
    int loop = 0;
    cin >> loop;

    vector<int> storage;

    for (int k = 0; k < loop; k++) {
        int num = 0;
        cin >> num;
        storage.push_back(num);
    }

    sort(storage.begin(), storage.end());

    for (vector<int>::iterator iter = storage.begin(); iter != storage.end(); iter++) {
        cout << *iter << '\n';
    }
}

// 	8180KB	672ms
void UsingSort(){
    int n = 0;
    cin >> n;

    vector<int> storage;

    int loop = n;
    while (loop--) {
        int num = 0;
        cin >> num;
        storage.push_back(num);
    }

    sort(storage.begin(), storage.end());
    
    vector<int>::iterator endPoint = unique(storage.begin(), storage.end());

    for (vector<int>::iterator iter = storage.begin(); iter != endPoint; iter++) {
        cout << *iter << '\n';
    }
}

//	48884KB	1428ms
void UsingSet() {
    set<int> sets;
    
    int loop = 0;
    cin >> loop;
    while (loop--) {
        int num = 0;
        cin >> num;
        sets.insert(num);
    }
    
    for (set<int>::iterator iter = sets.begin(); iter != sets.end(); iter++) {
        cout << *iter << '\n';
    }
}

int main(void) {
    UsingSortOnArray();
    return 0;
}