BOJ-백준 10989번 수 정렬하기 3

BOJ-백준 2751번 수 정렬하기 3

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

10989번: 수 정렬하기 3

✅ C++ 정답 코드 입니다. 더보기 클릭!

#include <iostream>
using namespace std;
int main() {
  int count[10001]={0};
  int n;
  cin >> n;
  for(int i = 0; i < n; i ++){
    int x;
    scanf("%d",&x);
    count[x] ++;
  }
  //cout << "Sorting..." << endl;
  for(int i=0; i<10001; i++){
    for( int j= 0;j<count[i]; j++){
      printf("%d\n",i);
    }
  }
}

📌 해설

데이터 갯수가 10,000,000개까지 주어 졌고, 나올 수 있는 수의 범위가 10000과 같거나 작은 자연수라고 범위가 정해졌으므로 계수 정렬(Counting Sort)으로 해결하는 문제입니다.

 

 

🚩참고

C++에서는 cin, cout이 느리기 때문에 시간초과될 수 있으므로 cin, cout대신 scanf, printf를 사용합니다. 

같은 코드라도 cin,cout에서 시간을 비효율적으로 쓴다면 10,000,000개의 데이터를 처리하는데 많은 시간을 소요하기 때문입니다. 

 

#include <iostream>
using namespace std;
int main() {
  int count[10001]={0};
  int n;
  cin >> n;
  for(int i = 0; i < n; i ++){
    int x;
    scanf("%d",&x);
    count[x] ++;
  }

1. 배열을 하나 선언하고 모두 0으로 초기화 합니다. ( count[10001] = 0 )

1-1. 나올 수 있는 수의 범위는 0~10000 이므로 count[0]~count[10000]이 될 수있도록 선언했고, 몇 개가 나왔는지 카운트 해야 하므로 0으로 초기화해주었습니다.

2. 테스트케이스의 갯수(n)을 입력받고 n만큼 반복하는 for문을 작성합니다. 모든 테스트케이스를 입력받고 count에 합산합니다. 

 

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

 3. 0~10000 까지 카운팅 한 결과를 차례대로 출력합니다. 

 

::

python으로 이미 풀었던 문제를

c++로 다시 풀어보니

파이썬이 얼마나 편리했는지 새삼 깨달아요ㅋㅋ