[백준] 10989번: 수 정렬하기 3 - 메모리 초과 문제 해결

간단한 정렬 문제

처음에 내가 쓴 코드는 메모리 초과문제가 있어서.... 내가 처음 쓴 코드와 메모리 초과 문제 해결 방안도 가져왔다.

10989번: 수 정렬하기 3

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

10989번: 수 정렬하기 3

 

메모리 초과 났던 내 코드

#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

(6) [C++] 백준 No.10989 : 수 정렬하기 3

풀이

* 입력받은 수를 전부 다 입력 받아서 저장하게 되면 제한된 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

백준 알고리즘 10989번: 수 정렬하기 3 [C++](카운팅 정렬)

다음 해설을 이해해보자.

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인 것은 제외시키고 배열 요소의 값만큼 배열의 인덱스 값을 출력하면 해결된다.

 

카운팅 소트 관련 포스팅 시간 내서 하자!

 

주의점) 큰 배열 선언할 때는 전역변수로 하세요

그 이유 찾고 올리겠습니다.