[JavaScript] 백준 5052 전화번호 목록 (JS)

전화번호 목록

📚 문제 설명

어떤 전화번호든 다른 전화번호의 접두어가 되지 않을 때 일관성이 있다고 표현한다.
예를들어 119, 11923 2개의 전화번호가 주어졌을 때, 119는 11923의 접두어이기 때문에 일관성이 없다.

전화번호 목록이 주어질 때, 해당 전화번호 목록이 일관성이 있는지 출력하라.

👨🏻‍💻 풀이 과정

전화번호 목록의 문자열을 그대로 sort()를 진행하면 어떻게 정렬이 될까?

113
98346
123440
12345
12340

위와 같은 문자열을 sort()한다고 하면 아래와 같이 될 것이다.

113
12340
123440
12345
98346

그럼 한가지를 알 수 있는데, sort()를 이용하여 문자열을 정렬했을 때,
만약 어떤 단어가 다른 단어의 접두어가 되려면 반드시 그 앞에 있는 단어라는 것이다.

예를 들어 word[i]의 접두어가 존재한다면,
그건 반드시 word[i - 1]라는 것이다.

이를 활용하여 코드를 작성하면 아래와 같다.
전체 풀이

let fs = require("fs");
let input = fs.readFileSync("./input.text").toString().trim().split('\n');

// let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
const TestCase = parseInt(input.shift());

const Check = () => {
    const N = parseInt(input.shift());
    const PhoneNumbers = input.splice(0, N);
    // 문자열 정렬.
    PhoneNumbers.sort();
    // 문자열이 정렬이 되면 , 바로 다음 단어만 확인하면 된다.
    for (let i = 0; i < PhoneNumbers.length - 1; i++) {
        // 만약 다음 단어 길이가 더 짧으면 확인하지 않아도됨
        if (PhoneNumbers[i + 1].length > PhoneNumbers[i].length) {
            // 이전 단어가 다음 단어 접두어인지 확인.
            if (PhoneNumbers[i + 1].slice(0, PhoneNumbers[i].length) === PhoneNumbers[i]) {
                return false;
            }
        }
    }
    return true;
};

const solution = () => {
    let answer = [];
    // 테스트 케이스 진행.
    for (let i = 0; i < TestCase; i++) {
        let possible = Check() ? 'YES' : 'NO';
        answer.push(possible);
    }
    console.log(answer.join('\n'));
};
solution();

🧐 후기

정렬 문제 분류에서 이 문제를 찾아서 풀면서 처음에는 이 문제가 왜 정렬 문제인지 이해가 되지 않았다.
그러나 2중 for 문을 돌며 풀이를 진행한 결과 당연하게도 틀리게 되었다.
그 후에 sort를 진행하면 자연스럽게 접두어가 바로 앞에 오게 된다는 것을 알게 되고 나서 그제야 왜 정렬 문제인지 알게 되었다.