[백준 알고리즘] 10989번 : 수 정렬하기 3, c++

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

10989번: 수 정렬하기 3

c++로 백준 10989번 문제를 풀어보겠다.

 

 

 

 

 

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

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

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

예제 입력 1 복사

10
5
2
3
1
4
2
3
5
1
7

예제 출력 1 복사

1
1
2
2
3
3
4
5
5
7

 

 

 

 

 

<문제 풀이>

 

처음에 작성한 코드는 다음과 같다.

 

visual studio에서는 내가 원하는 대로 결과가 나왔지만 백준 알고리즘에서는 '메모리 초과'라고 떴다.

이를 해결하기 위해서는 알고리즘의 복잡도를 해결해야 했고, 다른 방식으로 코드를 작성해야 했다.

 

 

따라서 마지막으로 작성한 코드는 다음과 같다.

 

1. N을 선언한 후 입력받는다.

2. 0-10000까지를 나타낼 수 있는 int 형의 배열을 선언한 후 모든 공간에 0을 저장한다.

3. 숫자를 N개 입력받아 그에 해당하는 인덱스의 배열 값을 0이 아닌 1로 저장한다.

(ex. 입력받은 숫자가 5이면 arr[5] 공간에 1을 저장한다.)

4. 인덱스 1부터 10000까지 돌며 저장된 값이 1이면 그 인덱스 숫자를 출력한다.

 

 

 

 

 

이 문제를 통해 알게된 점:

1. 알고리즘 복잡도를 해결하기 위해서는 

ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

다음과 같은 세 줄의 코드를 작성해야만 했다.

2. 배열을 재정렬하는 것이 아니라 10000개의 공간을 만들어 0 또는 1로 저장하고 그 인덱스 값을 사용하도록 해야했다.