[바미] 단어 정렬

문제

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

1181번: 단어 정렬

 

코드

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

// 중복 제거된 단어들을 길이와 사전 순으로 정렬
const sortedWords = Array.from(words).sort((a, b) => {
    if (a.length === b.length) {
        return a.localeCompare(b);  // 길이가 같으면 사전 순으로 정렬
    }
    return a.length - b.length;    // 길이에 따라 오름차순 정렬
});

// 결과 출력
console.log(sortedWords.join('\n'));

코드 설명

먼저 입력받은 단어들을 Set 객체에 저장하여 중복을 제거 해준 뒤, Array.from(words)를 통해 Set을 배열로 변환 한 후 sort() 메서드를 사용해 정렬합니다.

 

여기서 정렬 기준은 먼저 단어의 길이를 비교하고, 길이가 같을 경우 localeCompare() 메서드를 사용해 사전 순으로 정렬합니다.

 

그 후 정렬된 단어 배열을 줄 바꿈 문자로 연결해 최종 결과를 출력해줍니다.

문제 해설

주어진 문자열 리스트를 특정 기준에 따라 정렬하고 중복을 제거해야 하는 문제입니다. 

 

중복된 단어는 하나만 남겨야 하고, 정렬 기준은 첫 번째로 문자열의 길이가 짧은 것부터, 그리고 길이가 같을 경우 사전 순으로 정렬해주면 됩니다.

 

이를 위해 Set(), Array.from(), sort()를 사용하여 문제를 풀었습니다.

 

시간 복잡도

여기선 주로 sort() 함수에 의해 결정되기 때문에 O(N log N)이 됩니다.

여기서 N은 중복 제거 후 남은 단어의 개수를 의미합니다.

 

공간 복잡도

주어진 단어의 개수만큼 최대 공간을 필요로 하기 때문에  O(N)이 됩니다.

참고로 중복 제거가 있기 때문에 실제 사용 공간은 입력 개수보다 작을 수 있습니다.