수 정렬하기 3 풀이

문제 링크: https://www.acmicpc.net/problem/10989

백준 정렬 5단계 - 10989번 수 정렬하기 3을 풀어보았다.

 

풀이: 메모리와 시간에 제한이 있으므로, 적절한 정렬 알고리즘을 골라야 한다.

C++의 경우, ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)을 써서 시간을 줄였다.

파이썬의 경우, 입력값의 위치에 횟수를 저장하고 그 횟수만큼 출력시키게 했다.

 

C++

#include <iostream>

using namespace std;
int main()
{
	ios::sync_with_stdio(false); // 시간 줄이기용
  cin.tie(NULL);
  cout.tie(NULL);
	int n;
	cin>>n;
	int arr[10001] = {0};
	for(int i=0;i<n;i++)
	{
		int inp;
		cin>>inp;
		arr[inp]+=1;
	}
	for(int i=1;i<10001;i++)
	{
		for(int j=0;j<arr[i];j++)
		{
			cout<<i<<"\n";
		}     
	}
}

Python

import sys

n = int(sys.stdin.readline())
arr = [0 for i in range(10000)] # 입력값은 1부터 10,000까지
for i in range(n):
    arr[int(sys.stdin.readline())-1] += 1 # 입력값의 위치에 횟수 저장
for i in range(10000):
    if arr[i] != 0:
        for j in range(arr[i]): # 횟수만큼 출력
            print(i+1)

Java