[백준,C++] 10989 : 수 정렬하기 3

 

728x90

문제

---

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

SMALL

입력

---

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

반응형

출력

---

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

예제 입력 1

---

 

10 5 2 3 1 4 2 3 5 1 7

 

예제 출력 1

---

 

1 1 2 2 3 3 4 5 5 7

•  

 

처음에는 당연히

vector에 수를 입력 받고 sort 함수로 정렬했다

 

근데 처음보는 Memory 초과...

제한된 메모리를 고려하고 있어서 어떻게 해야 할지 고민해보았습니다.

요즘 컴퓨터는 용량과 메모리가 크기 때문에 공간 복잡도를 크게 신경 쓰지 않아도 되지만,

가전제품에 사용되는 IoT 장치나 예전 게임기, 닌텐도 등에서는 제한된 메모리를 가지고 있기 때문에,

제한된 메모리를 가지고 문제를 해결하는 것도 중요하게 여겨집니다.

그래서 떠오른 아이디어는 다음과 같습니다:

주어진 수가 10,000보다 작거나 같은 정수이므로,

입력 받은 수에 해당하는 주소에 ++를 해준 다음,

출력할 때 해당 수가 2이면 2번 출력하고,

3이면 3번 출력하는 방식으로 문제를 해결할 수 있을 것으로 생각했습니다.

그러나 이번에는 시간 에러가 발생했습니다.

그럴 때 쓰는

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

 

위 코드는 C와 C++의 표준 stream의 동기화를 끊어줌으로서서

따라서 CIN과 COUT의 속도가 빨라진다

 

그래서 최종적인 코드

#include <iostream>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int N;
    cin >> N;

    int numbers[10001]={0};

    for(int i=0;i<N;i++) {
        int in;
        cin >> in;
        input[in]+=1;
    }

    for (int i=1; i<10001;i++) {
        for (int j=0; j<numbers[i];j++) {
            cout << i << '\n';
        }
    }

}

 

 

<[백준] 7568 C++ : 덩치>

https://tonnykang.tistory.com/107

[백준,C++] 7568 : 덩치