[백준(BOJ)] 10989번 : 수 정렬하기 3 - C++[CPP]

www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3

 

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 정렬

 

 

---

 

⊙ 문제 접근 과정

 

이번 문제 정말 좋은 문제다. 시작해보자.

 

 

• 첫 번째 접근 과정 (첫 번째 알고리즘 고찰)

      정렬문제이니 제일 먼저 생각난 건 sort() 함수였다. 그래서 vector를 사용해 sort를 하려고 했다.

      그래서 열심히 헤더파일에 algorithm과 vector를 추가해줬고 코드를 짜고 문제없이 출력 값이 나왔다.

 

      하지만 결과는 메모리 초과

 

      공간 복잡도에 문제가 있다고 생각하여 sort() 풀이방식을 과감히 버렸다.

      수의 개수 N은 최대 10,000,000개이다. 입력값을 전부 저장하면 메모리가 남아나지 않는다.

 

      어떻게하면 공간을 많이 차지하지 않고 문제에 접근할 수 있을지 생각했다.

 

• 두 번째 접근 과정 (두 번째 알고리즘 고찰)

 

      그렇게 생각해낸게 count이다. 공간 복잡도, 또다시 메모리 초과가 나와서는 안 되기 때문에

      입력값을 전부 버리기로 결정했다. 그 대안으로 입력을 받을때마다 배열에 count를 올려 기록하기로 했다.

 

      헤더파일을 전부 버리고 코드를 깔끔하게 짜고 이중 for문을 통해 count를 구현해냈다.

 

      하지만 또 결과는 시간 초과

 

      이중 for문을 작성할 때 느낌이 안 좋긴 했다. 이번에는 시간 복잡도에서 문제가 생겼다.

      for문은 O(N)의 시간 복잡도를 가진다. 하지만 그 반복문 두 개를 겹쳐서 사용하면?

 

      O(N^2)의 시간 복잡도로 변하게 되고 그로 인해 TIMELIMIT에 걸렸다.

 

• 세 번째 접근 과정 (세 번째 알고리즘 고찰)

      아무리 생각해도 공간 복잡도와 시간 복잡도, 둘 다 잡을 수 있는 알고리즘을 생각할 수 없었다.

      그래서 알아본 결과

 

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 input[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<input[i];j++) {
            cout << i << '\n';
        }
    }

}

 

---

⊙ 결과

 

 

---

 

 

⊙ 마무리

 

 

시간 복잡도와 공간 복잡도에 대해 더 깊게 공부하고 생각하여 알고리즘을 구현해 문제에 접근하자