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

문제 설명

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

10989번: 수 정렬하기 3

 

해결 방향

N의 범위가 늘어났기 때문에

수 정렬하기1,2 처럼 vector와 sort를 사용하면 메모리 초과가 뜨게 된다

따라서 다른 방식으로 접근해야한다.

 

또한 cin cout을 사용하면 시간 초과가 뜨기 때문에 scanf 와 printf를 사용했다

cin cout을 사용하고싶다면 

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

를 main함수 안에 붙여주면 된다.

 

 

내가 작성한 코드이다.

#include<iostream>
#include<vector>
using namespace std;

int main()
{

	int N;
	scanf("%d", &N);

	vector<int>num(10001,0);


	for (int i = 0; i < N; i++)
	{
		int number;
		scanf("%d", &number);
		num[number]++;
	}

	for (int i = 0; i <10001; i++)
	{
		if (num[i] != 0) 
		{ 
			for (int j = 0; j < num[i]; j++)
			{ printf("%d\n", i); }
		}
	}

}

vector<int>num(10001,0);

N의 범위는 10,000,000까지 이지만

입력할 수 있는 숫자의 최대 크기는 10000이다.

따라서 해당 숫자를 몇개 입력 받는지를 판단하는 방식을 사용할 것이다.

10001크기의 vector num을 만들고 0으로 초기화해준다.

 

예를 들어 아래와 같이 입력한다면

 

N=10

1   10   1   4   2   12   334   2   2   2

 

배열에는 다음과 같이 저장될 것이다.

num[1]=2

num[10]=1

num[4]=1

num[2]=4

num[12]=1

num[334]=1

 

 

for (int i = 0; i < N; i++)
{
    int number;
    scanf("%d", &number);
    num[number]++;
}

위에 설명한 방식으로 배열을 채워나간다.

number를 입력받으면

number인덱스에 해당하는 num배열의 갯수가 하나씩 늘어난다.

for (int i = 0; i <10001; i++)
{
    if (num[i] != 0) 
    { for (int j = 0; j < num[i]; j++) { printf("%d\n", i); } }
}

num[i]==0이라면 해당 수 i는 입력받은 적이 없으므로 넘어간다.

0이 아니라면 배열에 저장된 수 만큼 i를 출력한다.