[JS] 2Level / 해시 / 전화번호 목록

문제 설명

https://school.programmers.co.kr/learn/courses/30/lessons/42577?language=javascript#

프로그래머스

문제 풀이 방법

해당 문제는 해시를 이용한 풀이가 정론이다.

각 문자별 해시테이블을 만들어준 뒤 phone_book의 요소들을 순회하며 문자를 slice 해가며 해시테이블에 존재하는지 확인한다.

 

이게 정론이지만 해당 문제는 sort 정렬을 이용해 쉽게 해결이 가능하다.

 

sort()를 이용하면 가장 첫자리 부터 끝자리 까지의 수와 전체 크기를 비교해 정렬해준다.

그렇게 되면 ["123", "456", "789", "1042", "0942", "0942334", "094233"]와 같은 배열의 정렬은 ['0942', '094233', '0942334', '1042', '123', '456', '789']와 같이 정렬된다.

 

사실 원래 내가 풀던 방법은 sort((a, b) => a.length  b.length)로 길이에 따라 정렬해주고, 정규 표현식을 이용해 검증하려 했다.

위와 같은 방법으로 풀이 했을 때는 순회를 2번에 정규표현식 test를 이용했기에 시간 초과가 발생할 수 밖에 없다.

그도 그럴것이 입력되는 배열의 길이가 최대 1,000,000 이기 때문.....

 

기존에 작성한 코드

function solution(phone_book) {
    let answer = true;
    phone_book.sort((a, b) => a.length - b.length);
    for(let i = 0; i < phone_book.length - 1; i++){
        const reg = RegExp('^'+phone_book[i]);
        for(let j = i + 1; j < phone_book.length; j++){
            if(reg.test(phone_book[j])){
                return false;
            }
        }
    }
    return answer;
}

 

정답 코드

const solution = (phone_book) => {
  phone_book.sort();

  for (let i = 0; i < phone_book.length - 1; i++) {
    if (phone_book[i + 1].indexOf(phone_book[i]) === 0) return false;
  }
  return true;
};