[C++] 10989번 수 정렬하기 3 - 문제풀이

 

● 문제 접근 과정

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

2. 시간 제한 : 5초 메모리 제한 : 8MB 이걸 배열로 해서 sort정렬로 풀라고 하면 4byte x  40,000,000 = 40MB 메모리 제한에 맞지 않는다.

3. 그래서 생각해 낸 게 10000보다 작거나 같은 수 까지 들어오기때문에 10001로 배열을 선언하고 해당 인덱스에 1씩을 늘려주고, for문을 돌려 출력하는 것을 생각하였다.

4. 4byte * 10001 =40004byte = 0.040004MB

● 구현

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
  ios::sync_with_stdio(false); // C와 C++의 동기화를 해제 C코드 작성 불가
  cin.tie(NULL);               // 코드 순서 무시 훨씬 빨라짐

  int N, idx;
  int cnt[10001] = {};
  cin >> N;

  for (int i = 1; i <= N; i++) {
    cin >> idx;
    cnt[idx] += 1;
  }

  for (int i = 1; i <= 10000; i++) {
    for (int j = 1; j <= cnt[i]; j++) {
      cout << i << "\n";
    }
  }
}

 

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

10989번: 수 정렬하기 3