<문제 소개>
<소스 코드>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <unordered_map>
#include <cmath>
#include <stack>
#include <queue>
#include <algorithm>
#include <cstdlib>
using namespace std;
int main()
{
// 쓰레드 환경이 아닐때 버퍼를 분리하여 처리속도를 빠르게 해줌
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N;
cin >> N;
vector<int> count(10001);
// 원소 입력
for (int i = 0; i < N; i++)
{
short x;
cin >> x;
count[x]++; // 입력된 수의 갯수를 파악
}
// 원소 출력
for (int i = 1; i <= 10000; i++)
{
for (int j = 0; j < count[i]; j++)
{
cout << i << "\n";
}
}
return 0;
}<풀이과정>
1. N을 입력받음
2. 갯수를 저장할 벡터 count를 vector<int>로 선언(short는 안됨!!!)
3. 입력되는 숫자의 범위가 10000보다 작거나 같은 자연수이므로 10000번째 인덱스까지 필요하기 때문에 벡터의 크기를 10001로 초기화 해준다.
4. N만큼 반복하며 입력 x를 벡터의 x번째 인덱스의 값을 1씩 증가시켜 해당 수의 갯수를 세어준다.
5. 1부터 10000까지를 반복하면서 해당 인덱스의 count 벡터의 값만큼 반복하여 해당 값을 출력해준다.
<코멘트>
처음에는 기수 정렬로 풀었다가 메모리초과가 났다. 그래서 질문게시판을 잠깐 보니 int형이 4바이트라서 모든 수를 int로 입력받으면 4*10,000,000 = 40MB이므로 메모리 초과가 날 수밖에 없었다. 근데 바보같게 short로 하면 되겠지 하고 똑같이 기수정렬에서 입력받는 숫자만 short로 바꾸고 풀었다. 당연하게도 또 메모리 초과가 나왔다.(2*10,000,000 = 20MB...) 도저히 잘 모르겠어서 검색의 힘을 빌려 풀었다.
입력되는 수가 10000보다 작은 것을 이용해서 갯수를 체크하여 풀면 되는 문제였다!
잘 풀었다고 생각하고 제출을 했는데 계속해서 틀렸다고 나와서 멘탈이 나갈 것 같았다... 알고보니 갯수를 담을 벡터 count의 자료형을 vector<short>로 설정한 것이 문제였다. 한 숫자가 10,000,000개 까지 나올 수 있는데 short는 그 숫자까지 입력받을 크기가 아니었던 것이었다. 그래서 vector<int>로 바꿔주어 해결했다!
<제출결과>
수많은 도전의 흔적,,,😥
