백준 10989문제 - 수 정렬하기 3 C++

📍 백준 10989문제 - 수 정렬하기 3 C++

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

 

---

🧩 문제 설명

이 문제는 오름차순 정렬을 구현하는 문제이다. 

하지만 sort()를 사용해도 시간초과가 나고 정렬알고리즘을 구현해도 시간초과가 났다.

그래서 어떻게 풀어야하는지 감을 못잡고 있었다. 

해법은 배열을 활용한 접근법에 있었다. 

내가 너무 정렬에만 꽂혀서 다른 방법을 생각조차 못해본 것이다. 

 

배열을 사용하면 문제를 정말 간단하게 해결할 수 있다. 

---

👍 이 문제에서 배운점

처음에는 무조건 배열에 수를 저장해두었다가 정렬알고리즘을 구현해서 다시 출력하는 방식으로 문제에 접근했다. (정석 방식)

하지만 이렇게 하면 무조건 메모리 초과나 시간초과가 뜬다. 

 

✅ 왜 시간초과가 날까? 

N의 최댓값이 10,000,000(천만개)이고 sort는 평균적으로 O(N log N)의 시간복잡도를 가진다. 

천만개를 정렬하면 약 2억번 이상의 연산을 해야하기 때문에 sort()도 정석적인 sort 알고리즘들도 시간초과가 걸리는 것이다. 

 

그렇다면 어떻게 문제를 해결 할 수 있을까?? 

 

✅ 문제 해결방법

이 문제에서 입력되는 수의 값은 1<=N<=10,000의 조건을 만족한다.

그럼 arr[10000]의 배열을 만들어서 각 index에 해당 숫자가 몇번 입력되는지 갯수를 저장해주고,

출력할 때는 해당 숫자의 갯수만큼 출력만 해주면 된다.

 

👉 즉, 카운팅 정렬을 사용하는 것이다. 

 

이렇게 하면 빠르게 문제를 해결할 수 있다. 

 

 

---

🧾내가 작성한 코드 

#include <stdio.h>
using namespace std; 

int arr[10001] = {0};

int main(){
    int n,idx ; 
    scanf("%d", &n);
    // 배열 입력받기 
    for(int i = 0; i<n ; i++){
        scanf("%d", &idx);
        arr[idx] += 1;
    }

    for(int i = 1; i<10001 ; i++){
        for(int j = 0; j<arr[i] ;j++){
            printf("%d\n", i);
        }  
    }
}

---