[바미] 나이순 정렬

문제

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

10814번: 나이순 정렬

코드

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
const N = parseInt(input[0], 10);
const members = [];

for (let i = 1; i <= N; i++) {
	// 입력된 문자열을 공백으로 분리하여 나이와 이름을 추출
    const [age, name] = input[i].split(' '); 
    // 추출된 나이와 이름, 그리고 순서를 객체로 만들어 배열에 저장
    members.push({ age: parseInt(age, 10), name, order: i }); 
}

// 나이순으로 정렬하고, 나이가 같을 경우 원래 순서(order)를 유지
members.sort((a, b) => a.age - b.age);

// 결과 출력
let result = '';
members.forEach(member => {
    result += `${member.age} ${member.name}\n`;
});

console.log(result.trim());

코드 설명

for (let i = 1; i <= N; i++) {
    const [age, name] = input[i].split(' '); 
    members.push({ age: parseInt(age, 10), name, order: i });
}

첫 번째 줄은 회원 수를 나타내기 때문에 두 번째 줄부터 시작하여 각 줄에서 회원의 정보를 읽어줍니다.

이 반복문은 1부터 N까지 반복하며, 각 회원의 데이터를 처리하는 반복문이 됩니다.

 

반복문 안에서는 i번째 줄의 입력 데이터(문자열)를 공백(' ')을 기준으로 분리합니다.

이렇게 해야 해당 줄의 나이와 이름이 공백을 기준으로 나누어져 배열로 반환 할 수 있습니다.

그 다음 분리된 배열의 첫 번째 요소(나이)와 두 번째 요소(이름)를 각각 age와 name 변수에 할당합니다.

 

할당이 끝나면 각 회원의 정보를 객체 형태로 구성하여 age는 파싱된 나이, name은 이름, order는 입력 순서를 object형태로 members 배열에 추가합니다.

 

여기서 order는 안정 정렬이 보장되지 않았을 때를 대비하여 나이가 같은 회원들을 가입 순서대로 정렬하기 위해 사용됩니다. (안정 정렬이 보장되면 별도의 사용 없이도 순서가 유지되므로 사용하지 않아도 됩니다.)

문제 해설

Array.prototype.sort() 메서드를 활용해 이를 간단하게 해결할 수 있는 문제입니다.

추가로 가입 순서는 입력 순서를 유지하기 때문에 안정 정렬(stable sort)이 보장된다면 추가적인 처리가 필요 없게 됩니다.

 

만약 사람들의 리스트가 있고, 이들을 나이순으로 정렬한 다음, 나이가 같은 사람들 사이에서는 가입 순서대로 정렬하고 싶다고 가정 할 때 정렬 알고리즘이 안정적이라면 나이로 처음 정렬을 수행한 후, 나이가 같은 사람들의 가입 순서는 그대로 유지됩니다.

안정 정렬(stable sort)은 정렬 알고리즘의 특성 중 하나입니다. 이 특성이 있는 정렬 방법을 사용하면, 동일한 값을 가진 요소들의 상대적인 순서가 정렬 전과 후에 동일하게 유지됩니다.
즉, 두 요소가 정렬 기준에 따라 동일하다고 판단될 때, 그 두 요소의 입력에 있던 순서가 그대로 유지된다는 의미입니다.

시간 복잡도

이 문제에서 시간 복잡도는 정렬 알고리즘의 복잡도 때문에 O(N log N)이 됩니다.

여기서 N은 배열의 길이, 즉 처리해야 할 데이터의 개수를 의미하고, log N은 각 데이터 요소를 분할하고 정복하는 과정에서 수행되는 연산의 횟수를 의미합니다.

공간 복잡도

입력받은 데이터를 저장하고 처리하는 데 필요한 공간이 데이터의 양에 비례하기 때문에 O(N)이 됩니다.

 

예를 들어, 회원이 N명이라면, 이들의 정보를 저장하기 위해 N개의 공간이 필요합니다.