JArchive 프로그래밍 일기

문제

수 정렬하기 3 백준 10989

"맞았습니다"코드

#include <bits/stdc++.h>
using namespace std;
int n, num;
int arr[10001];

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> n;
  for(int i = 0; i < n; i++){
    cin >> num; arr[num]++;
  }
  for(int i = 1; i <= 10000; i++){
    while(arr[i]){
      cout << i << '\n'; arr[i]--;
    }
  }
  return 0;
}

리뷰

이 문제는 sort() 함수를 쓰면 틀린다.
왜냐하면 메모리 제한이 8MB 이다.
int 는 4bytes니까. 문제 조건인 천 만개 배열을 선언하면 40MB 를 차지한다.
10000 보다 작은 자연수만 입력으로 들어오니까,
10000을 배열의 인덱스로 두고.
인덱스에 해당하는 숫자의 '개수'를 배열의 값으로 저장해서 해결하면 된다.

문제

수 정렬하기3 백준 10989번

리뷰

계수정렬(Counting sort) 를 써야 풀리는 문제다.

각 숫자의 개수를 배열 c에 저장한다. 입력받는 숫자는 10,000보다 작거나 같은 자연수이다.

배열 c는 10001 로 크기를 잡는다.

int N, num;
int c[10001];  // 개수를 저장할 배열 

    for(int i = 1; i <= N; i++){ // 1. 각 숫자의 개수를 센다  
        scanf("%d", &num);
        c[num]++;
    }

개수를 센 만큼 숫자 i를 출력 한다.

0개면 출력할 필요 없으니까, 1개 이상인 경우만 출력한다.

for(int i = 1; i < 10001; i++){     // 2. 개수만큼 i를 출력 

    if(c[i]){ // 개수 1이상이면 출력 

        for(int j = 0; j < c[i]; j++){
            printf("%d ", i);
        }
    }
}  

맞은 코드

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

int N, num;
int c[10001];  // 개수를 센다  

int main(void){

    scanf("%d", &N);

    for(int i = 1; i <= N; i++){ // 1. 각 숫자의 개수를 센다  
        scanf("%d", &num);
        c[num]++;
    }

    for(int i = 1; i < 10001; i++){     // 2. 개수만큼 i를 출력 

        if(c[i]){ // 개수 1이상이면 출력 

            for(int j = 0; j < c[i]; j++){
                printf("%d ", i);
            }
        }
    } 

    return 0;
}