[백준] 1181번 - 단어 정렬

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

문제 탐색하기

1) 문제 분석

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

2) 가능한 시간복잡도

(1) 입력 처리

단어 수 N만큼 반복하여 입력 → O(N)
중복 제거를 위해 Set에 삽입 → 평균 O(1) per item → 전체 O(N)

(2) 정렬 과정

sort() → 평균 O(N log N)
각 비교 시 문자열 길이 비교(정수 비교), 길이가 같으면 localeCompare() 호출 → 비교 연산은 O(1)

(3) 출력 과정

join() → O(N)
console.log() → O(1)

(4) 전체 시간 복잡도

O(N) + O(N log N) + O(N) = O(N log N)→ N ≤ 20,000이므로 충분히 빠르게 동작함.

3) 알고리즘 선택 이유

문제는 정렬 기반 문제로, 정렬 조건이 단순하고 명확하다.
중복 제거는 Set을 이용해 빠르게 처리 가능하다.
두 가지 기준(길이 → 사전순)을 동시에 고려하는 비교 함수를 sort()에 넘겨 해결할 수 있다.-> 따라서, 이 문제는 정렬 기반 알고리즘을 사용하는 것이 가장 직관적이고 효율적인 방법이다.

코드 설계하기

1. 실행 구조

1) 단어를 입력 받는다.

2) 단어 개수를 저장하는 첫번째값을 제거한다.

3) 중복을 제거한다.

4) 오름차순으로 정렬한다 (만약, 같은 길이의 문자열이라면 사전식으로 정렬한다.)

5) 결과를 출력한다.

2. 고민이 되었던 부분

1) 중복된 영어 단어는 한 번만 저장해야 한다.

-> new Set() 메소드를 사용하여 중복을 제거한다.

2) 길이가 같으면 영어 알파벳 순으로 정렬해야 한다

-> length 메소드를 사용하여 길이 비교 후 오름차순 정렬하고, 길이가 같은 경우 localeCompare 메소드를 사용하여 사전식으로 정렬한다.

localeCompare 메소드란?- 문자열을 사전식으로 비교할 때 사용하는 메서드이다. - 단순한 <, > 연산보다 정확하고 다국어 정렬을 지원한다.- 사용 방법 : a.localeCompare(b) - a < b면 → -1 (a가 b보다 앞에 있음) - a === b면 → 0 (a와 b가 깉음) - a > b면 → 1 (a가 b보다 뒤에 있음)- 예시 : array.sort((a, b) => a.localeCompare(b));

시도 회차 수정 사항

"어이없는 실수'

: 로컬에서 구현을 마치고 테스트를 진행한 결과 출력이 정상적으로 잘 나오는 것 같아서, 해당 코드를 제출했었다. 그러나 첫 번째 그리고 두 번째 모두 틀렸다는 결과가 나왔다. 아무리 코드를 보더라도 문제가 없었는데 말이다. 그런데 출력 결과를 비교해서 보니, 배열을 그대로 출력하는 것이 아닌, 배열의 각 값마다 줄바꿈을 한 결과가 출력되어야 했었다. 백준 결과에 있어서 아주 기본적인 부분이고, Day2문제를 풀면서 시스템콜을 여러 번 했을 때의 결과 저하에 대해 겪었던 부분이었음에도 불구하고 실수한 점이 어이가 없었다. 암튼 해당 부분을 해결하니 바로 정답을 마주할 수 있었다.

정답 코드

JavaScript

// 사용 언어 : Javascript

const fs = require('fs');

// 입력을 한 줄씩 받아와 문자열 배열로 변환
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

// 첫 줄은 단어의 개수 N → 필요 없으므로 제거
input.shift();

// 중복 제거: Set을 이용하여 동일한 단어는 하나만 남긴다
const setArr = new Set(input);

// 정렬 수행:
// 1. 길이 오름차순 정렬
// 2. 길이가 같다면 사전 순으로 정렬
const onlyStringArr = Array.from(setArr).sort((a, b) => {
  return a.length === b.length
    ? a.localeCompare(b)  // 길이가 같으면 사전순 비교
    : a.length - b.length; // 길이 기준 오름차순
});

// 결과를 개행 문자로 합쳐 출력
const result = onlyStringArr.join('\n');
console.log(result);

마무리하며

이번 문제도 어제와 같이 복잡한 알고리즘을 요구하는 문제라고 생각이 들지 않아서 평범하게 풀 수 있었다. 그래도 과정 속에서 성장할 수 있었던 점은 문자열 정렬에 있어서 동일한 문자열의 경우 사전식으로 정렬해야 하는 방식에 대해 고민하려고 했던 점이었다. 사실 이 부분이 해당 문제의 Main point였다. sort() 함수는 파라미터가 없으면 유니코드를 기준으로 정렬하여 알파벳 순서대로 정렬은 되지만, 내가 필요했던 상황은 문자열의 길이가 같은 경우에만 적용해야 했기에, 이 부분을 고려하는 데에 반절 이상의 시간을 사용했던 것 같다. 그러다 localeCompare이라는 메소드도 발견할 수 있던 점이 가장 인상 깊었다. 메소드를 잘 사용하는 것도 코테 응시에 있어 큰 영향을 줄 수 있따는 생각도 들어서 이번 기회에 여러 메소드들도 공부해보려고 한다.

최근 글