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

개요

문제 이름: 전화번호 목록 (5052)
문제 링크: https://www.acmicpc.net/problem/5052
플랫폼: 백준
알고리즘 분류: 정렬, 트리
소요 시간: 1시간 30분

 

문제 전문

설명

입출력

 

문제 풀이

해설

이 문제는 주어진 전화번호 목록이 일관성을 유지하는지 판단하는 문제입니다. 전화번호 목록이 일관성을 유지하려면, 어떤 번호가 다른 번호의 접두어인 경우가 없어야 합니다.

 

문제를 해결하기 위해서는 다음과 같은 접근 방식을 사용할 수 있습니다.

1. 전화번호 목록을 정렬합니다.
   1. 정렬을 하면 접두어 관계에 있는 번호들이 서로 인접하게 됩니다.
2. 정렬된 목록을 순회하면서 인접한 번호 쌍을 비교합니다.
   1. 현재 번호가 다음 번호의 접두어인 경우, 목록은 일관성이 없는 것입니다. (NO 출력)
   2. 현재 번호가 다음 번호의 접두어가 아닌 경우, 다음 번호 쌍을 비교합니다.
3. 순회가 끝날 때까지 접두어 관계가 발견되지 않으면, 목록은 일관성이 있는 것입니다. (YES 출력)

사실상 이 문제는 문자열 배열의 정렬과 접두어 관계 판별이라는 두 가지 주요 작업으로 구성됩니다.

 

문제에서 요구하는 사항은 다음과 같습니다.

• 첫째 줄에 테스트 케이스의 개수 t가 주어집니다. (1 <= t <= 50)
• 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어집니다. (1 <= n <= 10000)
• 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 하나씩 주어집니다.
• 전화번호의 길이는 길어야 10자리이며, 목록에 있는 두 전화번호가 같은 경우는 없습니다.
• 각 테스트 케이스에 대해서, 목록이 일관성을 유지하면 "YES", 그렇지 않으면 "NO"를 출력합니다.

즉, 주어진 전화번호 목록에서 한 번호가 다른 번호의 접두어인 경우가 있는지 검사하고, 그 결과를 출력하는 것이 이 문제의 요구사항입니다.

 

시도

1차 시도  (성공)

// 입력 파일을 읽어와서 문자열로 변환하고, 양쪽 공백을 제거한 후 줄바꿈으로 분리
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

// 첫 번째 줄에서 테스트 케이스의 개수를 읽어옴
let t = parseInt(input[0]);
// 현재 처리 중인 입력의 줄 번호를 추적
let currentIndex = 1;

// 각 테스트 케이스를 처리하는 루프
for(let i = 0; i < t; i++) {
    // 현재 테스트 케이스의 전화번호 개수를 읽어옴
    let n = parseInt(input[currentIndex]);
    
    // 현재 테스트 케이스의 전화번호들을 배열로 추출
    // currentIndex + 1: 전화번호가 시작되는 위치
    // currentIndex + 1 + n: 전화번호가 끝나는 위치
    let numbers = input.slice(currentIndex + 1, currentIndex + 1 + n);
    
    // 전화번호들을 정렬
    // 정렬하면 접두어 관계에 있는 번호들이 서로 인접하게 됨
    numbers.sort();
    
    // 일관성 여부를 저장하는 플래그
    let isConsistent = true;
    
    // 정렬된 전화번호들을 순회하면서 접두어 관계 확인
    for(let j = 0; j < n-1; j++) {
        // 현재 번호가 다음 번호의 접두어인지 확인
        // startsWith(): 문자열이 특정 문자열로 시작하는지 확인하는 메서드
        if(numbers[j+1].startsWith(numbers[j])) {
            isConsistent = false;  // 접두어 관계가 발견되면 일관성이 없음
            break;  // 더 이상 확인할 필요 없으므로 반복문 종료 
        }
    }
    
    // 결과 출력
    // 삼항 연산자를 사용하여 isConsistent 값에 따라 "YES" 또는 "NO" 출력
    console.log(isConsistent ? "YES" : "NO");
    
    // 다음 테스트 케이스를 처리하기 위해 현재 인덱스 업데이트
    // n개의 전화번호와 개수를 나타내는 한 줄을 더한 만큼 이동
    currentIndex += n + 1;
}

위 코드는 다음과 같은 과정을 통해 문제를 해결합니다.

1. 먼저 입력 데이터를 읽어옵니다. fs 모듈을 사용하여 '/dev/stdin'에서 입력을 읽어오고, 이를 문자열로 변환한 후 줄바꿈으로 분리합니다.
2. 첫 번째 줄에서 테스트 케이스의 개수 t를 읽어옵니다. parseInt를 사용하여 문자열을 정수로 변환합니다.
3. currentIndex 변수를 사용하여 현재 처리 중인 입력 줄의 위치를 추적합니다. 초기값은 1로 설정합니다.
4. t만큼 반복하는 for 루프를 사용하여 각 테스트 케이스를 처리합니다.
   1. 현재 테스트 케이스의 전화번호 개수 n을 currentIndex를 사용하여 읽어옵니다.
   2. slice 메서드를 사용하여 현재 테스트 케이스의 전화번호들을 numbers 배열로 추출합니다.
   3. sort 메서드를 사용하여 numbers 배열을 정렬합니다. 이렇게 하면 접두어 관계에 있는 번호들이 서로 인접하게 됩니다.
   4. isConsistent 변수를 사용하여 일관성 여부를 저장합니다. 초기값은 true로 설정합니다.
   5. for 루프를 사용하여 정렬된 전화번호들을 순회하면서 접두어 관계를 확인합니다.
      1. startsWith 메서드를 사용하여 현재 번호가 다음 번호의 접두어인지 확인합니다.
      2. 접두어 관계가 발견되면 isConsistent를 false로 설정하고 break문으로 반복문을 종료합니다.
   6. 삼항 연산자를 사용하여 isConsistent 값에 따라 "YES" 또는 "NO"를 출력합니다.
   7. currentIndex를 n + 1만큼 증가시켜 다음 테스트 케이스를 처리할 준비를 합니다.

 

사용된 주요 메서드

• String.prototype.split(): 문자열을 지정된 구분자를 기준으로 분할하여 배열로 반환합니다. split(separator[, limit]) 방식으로 사용합니다.
• Array.prototype.slice(): 배열의 일부분을 추출하여 새로운 배열을 반환합니다. slice(start, end) 형태로 사용되며, start부터 end 바로 앞까지의 요소를 추출합니다. end는 생략 가능합니다.
• Array.prototype.sort(): 배열의 요소를 정렬합니다. 기본적으로 유니코드 코드 포인트 순서로 정렬되며, 숫자 배열의 경우 문자열로 변환된 후 정렬됩니다. 비교 함수를 인자로 전달하여 정렬 순서를 제어할 수 있습니다.
• String.prototype.startsWith(): 문자열이 특정 문자열로 시작하는지 확인합니다. startsWith(searchString[, position]) 형태로 사용되며, searchString으로 시작하는지 여부를 불리언 값으로 반환합니다. position은 검색을 시작할 위치로, 생략하면 기본값은 0입니다.

 

시간 복잡도와 공간 복잡도

• 시간 복잡도: O(T * (N log N))
  • 전체 테스트 케이스의 수가 T이고, 각 테스트 케이스의 전화번호 수가 최대 N일 때, 각 테스트 케이스마다 전화번호를 정렬하는데 O(N log N)의 시간이 소요됩니다.
  • 정렬 후 일관성 검사를 위해 배열을 한 번 순회하므로 O(N)의 시간이 추가로 소요됩니다.
  • 따라서 전체 시간 복잡도는 O(T * (N log N + N)) = O(T * (N log N))입니다.
• 공간 복잡도: O(N)
  • 각 테스트 케이스마다 전화번호를 저장하기 위한 배열 numbers가 사용되며, 최대 N개의 전화번호가 저장될 수 있습니다.
  • 그 외의 변수들은 상수 개수만큼 사용되므로 공간 복잡도에 영향을 주지 않습니다.
  • 따라서 공간 복잡도는 O(N)입니다.