[알고리즘] 프로그래머스 알고리즘 고득점 Kit - [JavaScript] 전화번호 목록

https://school.programmers.co.kr/learn/courses/30/lessons/42577

프로그래머스

본 포스팅에서 다루는 문제는 위 프로그래머스 링크를 통하여 문제 확인 및 풀이가 가능합니다!

 

짧은 문제 분석

•  입력 값으로는 String List 타입의 phone_book이 주어집니다.
  ex) ["119", "97674223", "123"]
• phone_book 내부의 전화번호 중 한 번호가 다른 번호의 접두사인 경우가 있으면 false, 없으면 true를 반환합니다.
  ex) ["119", "119212323] --> false / ["123", "456"] --> true
• phone_book의 길이, 즉 배열의 원소의 수 n은 1 <= n <= 1,000,000 입니다.

프로그래머스 고득점 Kit에서는 해당 문제를 해시로 분류하였지만 본 문제 풀이에서는 단순히 배열을 순회하는 방법으로 풀이하였습니다. 

n의 최대 크기가 100만이기 때문에 주요 연산을 최대한 줄이는 것이 해당 문제의 키 포인트라고 생각됩니다.

 

 

1. 첫 번째 코드 ( 정확성: 70.8 / 효율성 8.3)

function solution(phone_book) {
    let prevList = [];
    
    for (let phone of phone_book) {
        for (let prev of prevList) {
            if (prev.length > phone.length)
                continue;
            
            if (prev === phone.substr(0, prev.length))
                return false;           
        }
        // 순회가 끝났으면 비교 목록인 prevList에 추가
        prevList.push(phone);
    }
    return true;
}

 

 정확성 테스트의 8, 9, 15번 케이스와 효율성 테스트의 3, 4번 케이스를 실패한 코드입니다.

 

 배열을 for 문을 통하여 순회하면서 현재 원소(phone)와 이전 배열 원소들(prevList의 모든 원소)과 비교하며 접두사가 되는 경우를 판단합니다. 접두사라는 조건을 만족하지 않는 경우에는 불필요한 substr 함수 실행을 줄이기 위하여 prev와 phone의 length를 비교하여 prev가 접두사가 될 수 없는 경우에는 continue를 하도록 코드를 작성하였습니다.

 

 

2. 두 번째 코드 ( 정확성: 83.8 / 효율성 8.3)

function compare(a, b) {
    return a.length - b.length;
}

function solution(phone_book) {
    let prevList = [];
   
    phone_book.sort(compare);
    
    for (let phone of phone_book) {
        for (let prev of prevList) {
            if (prev === phone.substr(0, prev.length))
                return false;           
        }
        // 순회가 끝났으면 비교 목록인 prevList에 추가
        prevList.push(phone);
    }
    return true;
}

 

 정확성 테스트의 실패 케이스를 해결하고 효율성 테스트의 3, 4번 케이스를 실패한 코드입니다.

 

  첫 번째 코드에서 정확성 부분만 개선된 케이스입니다. phone_book을 길이가 짧은 순으로 먼저 정렬한 뒤 배열을 순회합니다. 길이가 짧은 원소부터 순차적으로 접근하여 그 다음 원소와 비교하기 때문에 무조건적으로  prev는 phone보다 짧거나 같습니다. 이를 통하여 for문을 순회하면서 진행했던 불필요한 length 접근 및 비교 연산을 줄일 수 있습니다.

 사실 첫 번째 코드와 논리적으로 동일한 로직이라고 생각하였는데 정확성 부분에서 차이가 나는 이유를 여러 테스트 케이스를 추가하면서 생각해보았는데 아직도 조금 모호한 부분입니다. 두 코드의 차이점을 알고 계신 분이라면 피드백 주시면 감사하겠습니다 :)

 

 

3. 세 번째 코드(정답 코드)

function solution(phone_book) {
    phone_book.sort();
    
    for (let i = 0; i < phone_book.length - 1; i++)
        if (phone_book[i] == phone_book[i + 1].substr(0, phone_book[i].length))
            return false;
    
    return true;
}

 

 첫 번째와 두 번째 코드의 시간 초과 문제를 해결하기 위하여 코드를 전체적으로 수정하였습니다.

  

 사실 문제의 입력값으로 주어지는 것이 String List 라는 점이 위 코드의 키 포인트입니다. 기본적으로 제공하는 sort 메소드를 이용하게 되면 문자열을 기준으로 비교를 진행하기 때문에 숫자의 앞 자리부터 비교를 합니다.

 예를 들어 "1", "2", "10", "11", "100", "101", "20"를 정렬할 경우에는 "1", "10", "100", "101", "11", "20"으로 바뀌게 됩니다. 두 번째 코드처럼 길이 순으로 정렬을 진행한 것보다 더욱 빠르게 접두사 관계인 서로를 찾을 수 있는 것입니다. 

 문제에서 요구하는 바와 문자열 정렬의 동작 방식을 정확하게 이해한 사람들이라면 쉽게 해답에 도달할 수 있었을 것이라 생각됩니다.

 

 

 

4. 마치며...

 입력값으로 넘어온 데이터의 양이 많을 때, 연산 횟수를 줄이기 위한 아이디어를 떠올리는 것이 가장 중요했던 문제였습니다. 또한, 이러한 연산 횟수를 줄이기 위해서 가장 먼저 살펴보아야 할 것은 입출력 형태(이번 문제에서는 문자열 배열) 그리고 구하고자 하는 결과 값과의 관계가 아니었나 생각이 듭니다.

 다음에는 본 문제가 분류된 풀이 방법인 해싱! 으로도 새로 풀이를 진행하여 포스팅을 해보도록 하겠습니다. 긴 글 읽어주셔서 감사합니다 :)