[백준] 10814번 - 나이순 정렬

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

문제 탐색하기

1) 문제 분석

가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다.
출력은 회원의 나이를 오름차순, 나이가 같으면 먼저 가입한 순으로 한다.

2) 가능한 시간복잡도

(1) 입력 처리

회원 수 N만큼 반복 → O(N)
각 줄을 split하고 Member 객체 생성 → O(1)
총 입력 처리 비용 → O(N)

(2) 정렬 과정

JavaScript의 .sort()는 평균적으로 O(N log N)
나이 기준 정렬, 나이가 같을 경우 입력 순서(idx) 비교 → 비교 연산은 O(1)

(3) 출력 과정

map + join → O(N)
console.log 1회 → O(1)

(4) 전체 시간 복잡도

O(N) + O(N log N) + O(N) = O(N log N)→ 충분히 효율적인 시간 복잡도로, N이 최대 100,000이어도 통과 가능

3) 알고리즘 선택 이유

회원 수는 최대 100,000명으로 꽤 많지만,
정렬 기준이 단순하며 .sort()로 해결 가능하고,
안정 정렬이 필요해 입력 순서를 함께 저장 (idx 활용),
전체적으로 정렬 기반 알고리즘을 사용하는 것이 적절하다 판단됨.

따라서, 이 문제는 정렬 알고리즘 기반의 해결 방식을 선택했다.

코드 설계하기

회원 정보를 입력 받는다.
회원 정보를 담을 클래스를 선언한다.
입력 받은 회원 정보의 2번째 값부터 끝까지 반복하며, Member 객체로 변환하고 저장한다.
나이가 적은 순, 나이 같으면 입력 순서가 빠른 순으로 정렬한다.
각 회원 정보를 '나이 이름' 형식으로 출력한다.

시도 회차 수정 사항

사실 로컬에서 여러 시도를 진행해보면서 정상적인 출력이 잘 나오는 것을 확인했고, 백준에 접속하여 해당 코드를 제출하여 채점한 결과 한 번만에 통과를 할 수 있었다. 그러나 한가지 아쉬웠던 점은 아래 사진처럼, 실행 시간이 3000ms대가 나왔다는 점이었다. 물론 문제에서 시간 제한을 3초로 두긴 했지만, 꽤나 오래 걸리는 것을 보면서 시간을 단축하고 싶었다.

출력 시간이 3000ms를 넘어간다.

그래서 서칭도 하면서 어떤 점이 오래 걸렸을지 고민하는 시간을 가졌다. 사실 '생각 후 코딩' 과정에서 생각 단계에서 알고리즘을 고민할 당시에 로직 상으로는 시간을 크게 잡을만한 부분은 발견하지 못했었다. 그러나 시간이 오래 걸렸던 이유를 찾을 수 있었다.

바로 결과 출력을 하는 'console.log' 때문이었다. console.log()를 N번 호출하는 방식은 Node.js에서 굉장히 느리다는 것을 알게 되었다. stdout에 매 번 출력할 때마다 시스템 콜이 일어나길 때문에, 입력이 많아질수록 심각하게 느려진다고 했다. 그래서 출력 자체를 console.log로 N번 호출하지 않고, 하나의 문자열로 만들어서 한 번만 출력할 수 있도록 코드를 수정했다.

JavaScript

// 기존 코드
sortedMemberInfos.forEach((data) => console.log(data.age + " " + data.name));

// 수정 코드
const result = sortedMemberInfos.map(data => `${data.age} ${data.name}`).join('\n');
console.log(result);

그 결과 실행 시간이 90% 이상 낮아진 결과를 마주할 수 있었다. (대성공)

출력 시간이 300ms대가 되었다.

더 나아가서 추가적으로 몇 가지 더 고민했던 사항들도 요약해서 공유한다.

고민1 : 입력받은 값을 어떻게 파싱할 수 있을까? -> 입력은 fs.readFileSync + split으로 처리 (백준 표준 입력 방식)한 뒤에 클래스를 선언하여 할당.
고민2 : 파싱된 데이터를 어떻게 조건대로 정렬할 수 있을까? -> 안정 정렬이 필요하므로, 나이가 같을 경우 입력 순서를 기억하는 idx 사용, sort() 함수를 사용
고민3 : 실행 시간이 무려 3000ms대, 어떻게 줄일 수 있을까? -> console.log를 N번 호출하면 느려지므로, join 후 한 번만 출력하여 성능 개선

정답 코드

JavaScript

// 사용 언어 : Javascript

const fs = require('fs');

// 입력을 한 줄씩 받아와 문자열 배열로 변환
// 첫 줄은 회원 수 N, 그 다음 줄부터는 [나이 이름] 형식의 회원 정보
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

// Member 클래스 정의: 나이, 이름, 입력된 순서(idx)를 속성으로 가짐
class Member {
    constructor({ age, name, idx }) {
        this.age = age;
        this.name = name;
        this.idx = idx; // 입력 순서를 기억하여 안정 정렬을 흉내냄
    }
}

// 회원 정보를 담을 배열
let memberInfos = [];

// 입력 줄의 두 번째 줄부터 끝까지 반복하며 Member 객체로 변환
for (let i = 1; i < input.length; i++) {
    const data = input[i].split(" "); // 공백으로 나이와 이름 분리
    const memberInfo = new Member({ age: Number(data[0]), name: data[1], idx: i }); // age를 숫자로 변환
    memberInfos.push(memberInfo); // 배열에 저장
}

// 정렬 수행: 
// 1. 나이가 적은 순으로 정렬
// 2. 나이가 같으면 입력 순서(idx)가 빠른 순으로 정렬
const sortedMemberInfos = memberInfos.sort((a, b) => a.age - b.age || a.idx - b.idx);

// 출력 최적화:
// 각 회원 정보를 "나이 이름" 형식으로 만든 후 join으로 하나의 문자열로 병합
const result = sortedMemberInfos.map(data => `${data.age} ${data.name}`).join('\n');

// 출력은 단 한 번만 console.log로 실행 (속도 개선)
console.log(result);

마무리하며

해당 문제의 경우에는 특정 알고리즘 개념을 사용하진 않았다. 그냥 단순한 정렬 알고리즘을 사용하였고, 조건 기반 정렬 문제이다보니, 이를 위해 안정 정렬을 고려한 이중 조건 정렬을 사용하게 되었다. 문제를 보고 바로 머릿 속에 그림이 그려졌을 정도로 큰 어려운 문제로는 다가오지 않았던 것 같다. 그래서일까 한편으로는 이렇게 푼게 과연 맞는 것일지 의문이 들기도 했다. 아! 그리고 해당 문제를 풀면서 중간중간에 '어떻게 해결하지?'라는 포인트가 떠오를 때마다 기록하면서 해당 포인트에 대한 해결방법을 고민하는 점도 인상 깊었다. 이런 식으로 '생각 후 코딩'에 익숙해지며 3주 간 코테에 대한 흥미를 더 끌어 올렸으면 좋겠다.

추가로 ㅎㅎ 사실은 자정을 넘어가면서 문제를 풀게 되었다. 2일차 문제를 푼 것은 맞지만, 정신은 1일차의 연장선이다. 그래서 내일은 다른 문제들도 한 번 풀어볼까 한다.

최근 글