10989번: 수 정렬하기 3

 

 

 

 

 

풀이

 

조건이 좀 까다로운 문제입니다.

 

조건을 만족하기 위해서 시간,공간 복잡도가 O( n + k )인 계수 정렬을 사용하였고 cnt[i]가 0이 아닐때에만 증감식을 수행합니다.

 

 

 

 

 

자바

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException  {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(br.readLine());
        int[] cnt = new int[10001];

        for (int i = 0; i < n; i++) {  
            cnt[Integer.parseInt(br.readLine())] ++;
        }
        br.close();

        for (int i = 1; i < 10001; i++) {
             while(cnt[i] > 0){
                sb.append(i).append('\n');
                cnt[i]--;
            }
        }
        System.out.print(sb);
    }
}

 

 

 

 

 

파이썬

from sys import stdin

n = int(input())

cnt = [0] * 10001

for i in range(n):
    cnt[int(stdin.readline())] += 1 

for i in range(10001):
    if cnt[i] != 0:      
        for _ in range(cnt[i]):
            print(i)