백준 10989 번 문제 풀이 C++ :수 정렬하기 3

#77. 백준 10989번 문제 풀이: 수 정렬하기 3

N개의 수를 오름차순으로 정렬하는 프로그램 작성 *단, 메모리 제한 8MB. 입력: 첫 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000), 둘째 줄부터 N개의 수가 한 줄에 하나씩 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. 출력: 첫 줄부터 N개의 줄에 오름차순으로 숫자를 출력

입력/출력

--입력--
10
5
2
3
1
4
2
3
5
1
7
--출력--
1
1
2
2
3
3
4
5
5
7

문제풀이+해설

이 문제의 요지는 메모리 제한이 존재한다.
수의 최대개수가 천만개로 메모리 제한보다 많다.
즉, 메모리 제한으로 배열이나 리스트에 저장하는 게 불가능 하다.

이 문제의 해결 요지는 수의 범위가 10,000 이하의 자연수라는 것이다.
즉, 10,000개의 배열을 선언해서 배열의 인덱스값을 숫자로 간주하고, 각 배열에 카운트값 만큼이 숫자라고 간주하면 된다.
예를 들어, 숫자 최대 범위가 5까지만 있다고 가정하고 아래와 같이 되어 있다면,
   ① ② ③ ④ ⑤  : 인덱스값(인덱스를 숫자라 간주)
[0,1,2,0,0,1] : 값이 존재하는 카운트 배열
①인덱스 1개, ②인덱스 2개, ③,④인덱스 0개, ⑤인덱스 1개,
숫자로 간주하면 1,2,2,5 가 된다.

이 알고리즘은 숫자의 범위가 크지않게 한정 되어 있을 경우 사용하면 매우 효과적이다.C++에서는 시간초과가 걸려서 입력속도를 빠르게 하기 위해 아래 코드를 넣어주었다.

  ios::sync_with_stdio(false);
  cin.tie(NULL); 
//입력 속도를 위해 표준C 입출력과 연동을 제거함

code sol.

코드편집/실행

#include <iostream>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL); // 입력 속도를 위해 표준C 입출력과 연동을 제거함
    
  int i, j, n, N;
  int ns[10001] = {0}; // 0값으로 초기화된 숫자범위 크기의 배열 
  
  cin >> N; // 수의 개수 입력 받아 정수로 변환해 대입
  for(i = 0; i < N; i++) { // 개수만큼 루프
    cin >> n; // 숫자를 하나씩 입력받음.
    ns[n] += 1;  // 숫자에 해당하는 인덱스의 값을 증가시킴
  }  
  for(i = 0; i < 10001; i++) { // 숫자의 범위내에서 루프
    if(ns[i] != 0) { // 배열값이 0보다 크면..숫자가 있는 것으로 간주
      for(j = 0; j < ns[i]; j++) { // 숫자가 있는 카운트 만큼
        cout << i << "\n"; // 한줄에 하나씩 출력
      }    
    }   
  }
  return 0;
}