[바미] 수 정렬하기 2

문제

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

2751번: 수 정렬하기 2

코드

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
const N = parseInt(input[0], 10);
const numbers = input.slice(1, N + 1).map(Number);

// 오름차순 정렬
numbers.sort((a, b) => a - b);

// 결과 출력
let result = '';
numbers.forEach(number => {
    result += `${number}\n`;
});

console.log(result.trim());

코드 설명

numbers.sort((a, b) => a - b)에서  숫자 배열을 오름차순으로 정렬 한 뒤, result 배열에 출력할 문자열을 누적해줍니다.

각 숫자뒤엔 줄바꿈 문자를 추가해주고, 출력 시 공백을 제거하기 위해 trim()을 호출합니다.

문제 해설

이 문제는 주어진 N개의 수를 오름차순으로 정렬하는 것이지만 입력 수의 범위가 최대 1,000,000개의 큰 입력 수를 가진 문제입니다. 

이를 해결하기 위해 Javascript의 기본 정렬 함수인 sort()함수를 사용하여 풀었습니다.

 

시간 복잡도

sort() 메서드의 시간 복잡도는 일반적으로 O(N log N)입니다.

여기서 N은 배열의 길이를 의미합니다.

공간 복잡도

주어진 입력을 저장하는 데 O(N)의 공간이 필요하고, 추가적으로 결과를 출력하기 위한 문자열을 저장하는 데도 O(N)의 공간이 필요합니다. 따라서 전체 공간 복잡도는 O(N)입니다.