[백준] 10989번: 수 정렬하기 3 - 메모리 초과 문제 해결
간단한 정렬 문제
처음에 내가 쓴 코드는 메모리 초과문제가 있어서.... 내가 처음 쓴 코드와 메모리 초과 문제 해결 방안도 가져왔다.
10989번: 수 정렬하기 3
https://www.acmicpc.net/problem/10989
메모리 초과 났던 내 코드
#include <iostream>
#include <algorithm>
using namespace std;
int arr[10000000];
int main(void)
{
cin.tie(0);
ios::sync_with_stdio(0);
int N;
cin >> N;
for (int i = 0; i < N; i++)
{
cin >> arr[i];
}
sort(arr, arr + N);
for (int i = 0; i < N; i++)
{
cout << arr[i] << '\n';
}
return 0;
}
메모리 초과문제에 관한 링크
https://www.acmicpc.net/board/view/122801
보기 편하라고
버블로는 안 된다.
counting sort(카운팅 소트) 찾아보자. (이거 포스팅 따로 쓰겠습니다.)
다른 사람 풀이 참고
https://ldgeao99.tistory.com/344
풀이
* 입력받은 수를 전부 다 입력 받아서 저장하게 되면 제한된 8MB의 메모리를 초과해버린다.
숫자를 카운트 해두었다가 표준출력으로 출력만 해주는 방식을 사용해야한다.
(10^7 * 4byte = 40MB이므로)
# C++
#include <iostream>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int T;
cin >> T;
int arr[10001] = {0};
// 숫자 개수 카운트
for(int i = 0 ; i < T; i++){
int a;
cin >> a;
arr[a] += 1;
}
// 각 숫자를 개수만큼 출력해주기
for(int i = 1 ; i <= 10000; i++)
for (int j = 0; j < arr[i]; j++)
cout << i << "\n";
}
더 자세한 풀이를 보자면
https://travelerfootprint.tistory.com/145
다음 해설을 이해해보자.
1. 코드 (바로 아래 코드의 주석은 내가 새로 달았다.)
#include <iostream>
#include <algorithm>
using namespace std;
int main(void)
{
cin.tie(0);
ios::sync_with_stdio(0);
int arr[10001] = { 0, }; /* 모두 0으로 초기화 */
int N;
cin >> N;
for (int i = 0; i < N; i++)
{
int input;
cin >> input;
arr[input]++; /* i의 등장횟수는 arr[i]에다가 대입*/
}
for (int i = 1; i < 10001; i++) /*1부터니 0은 제외*/
{
if (arr[i]) /* 등장횟수 관련 배열 arr => 만약 arr[i]가 0이라면 i가 0번 나왔다는 말*/
{
for (int j = 0; j < arr[i]; j++) /*i의 등장횟수 만큼 i를 찍어라*/
cout << i << '\n';
}
}
return 0;
}
2. 풀이
수의 범위가 10000보다 작거나 같은 자연수이기 때문에 카운팅 정렬을 이용하여 문제를 해결해보겠다.
ios::sync_with_stdio(false); //C입출력 방식 사용제한
cin.tie(NULL); //앞에서 cout으로 출력을 한다면 출력전에 입력부터 진행
위 코드를 넣어서 프로그램의 입출력 속도를 증가시켰다.
int arr[10001] = { 0, };
int n;
cin >> n;
그리고 배열을 10000 크기만큼 선언과 동시에 0으로 초기화시켜준다. 그리고 사용자에게 입력 횟수를 변수 n으로 통해 입력받는다.
for (int i = 0; i < n; i++)
{
int input;
cin >> input;
arr[input]++;
}
그리고 사용자에게 n번만큼 값을 input값을 입력받는데 input 위치에 해당하는 배열의 값을 1씩 증가시킨다. 이렇게 되면 해당하는 배열의 값과 인덱스 값을 통해 어떠한 수가 얼마만큼 입력되었는지 확인할 수 있다. (예를 들면 1이 5개면 index=1인 위치의 배열 값은 5 이런 식)
for (int i = 1; i < 10001; i++)
{
if (arr[i])
for (int j = 0; j < arr[i]; j++)
cout << i << '\n';
}
그리고 배열을 전체 조회를 하는데 배열 요소의 값이 0인 것은 제외시키고 배열 요소의 값만큼 배열의 인덱스 값을 출력하면 해결된다.
카운팅 소트 관련 포스팅 시간 내서 하자!
주의점) 큰 배열 선언할 때는 전역변수로 하세요
그 이유 찾고 올리겠습니다.