반응형
백준 온라인 저지의 10989번 문제입니다.
문제 분류는 [정렬]로 분류되어 있습니다.
문제 링크 : https://www.acmicpc.net/problem/10989
문제 :
N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.
입력 :
첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.
출력 :
첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.
풀이 :
- 이 문제는 Counting sort 알고리즘을 적용해서 푸는 문제입니다.
- Counting sort, 거창해 보이지만 이 문제를 풀어보면 "아 이거구나 ㅋ"라고 감이 오실겁니다.
- 해당 알고리즘에 대해선 추후에 정리해 보도록 하겠습니다만,
- 당장 자세한 설명이 알고싶으신 분은 아래 링크에 설명이 잘 되어있습니다.
(이분 설명 잘하시는듯..)
https://bowbowbow.tistory.com/8
핵심은 아래와 같습니다.
1. 먼저 최대 크기+1의 배열을 만들고 0으로 초기화,
2. 값이 들어올 때 마다 해당 배열의 "인덱스"의 값을 +1시켜줌.
- 추가적으로, iostream의 cout을 사용하였더니 시간 초과가 발생합니다.
- cout과 printf의 실행속도의 차이가 얼마나 큰지 알 수 있는 문제였습니다.
소스코드 :
#include<iostream>
using namespace std;
#define MAX_SIZE 10001
int main()
{
int narr[MAX_SIZE] = { 0, };
int i, j;
int num, num1;
scanf("%d", &num);
for (i = 0; i < num; i++)
{
scanf("%d", &num1);
narr[num1]++;
}
for (i = 0; i < 10001; i++)
{
if (narr[i])
for (j = 0; j < narr[i]; j++)
{
printf("%d\n", i);
}
}
return 0;
}
반응형
'Dev > [Algorithm]' 카테고리의 다른 글
[Algorithm] [C++] 백준 10171번 고양이 (0) | 2020.10.22 |
---|---|
[Algorithm] [C++] 백준 2798번 블랙잭 (0) | 2020.10.22 |
[Algorithm] [C++] 부채꼴 범위 안의 적 판별하기 (0) | 2020.05.28 |
[Algorithm] [C++] 백준 1011번 Fly me to the Alpha Centauri (0) | 2020.04.14 |
[Algorithm][C++] 프로그래머스 코딩테스트 연습 - 라면공장 (0) | 2020.02.19 |