전화번호 목록

코딩 테스트 문제

프로그래머스

 

문제 접근)
phone_book의 길이가 1~ 10^7 이므로 시간복잡도 O(N^2)미만의 알고리즘으로 해결해야합니다. (2중 for문 이상 사용 x)

 

정답 및 풀이

정답 

function solution(phone_book) {
    phone_book.sort();
    return !phone_book.some((phone, idx) => phone_book[idx + 1]?.startsWith(phone))
}

 

풀이

phone_book을 sort() 정렬하면 인접한 숫자들끼리 가까운 위치에 놓이게 됩니다.

ex) ["119", "97674223", "1195524421"] -> ["119", "1195524421", "97674223"]

some을 이용해서 인접한 인덱스의 phone을 비교하여, startsWith 함수를 이용해 앞의 접두사가 비슷한지 체크하는 방식으로 해결하였습니다. some은 하나만 만족해도 true가 출력되는데 문제에서는 하나만 겹치는 접두사가 있으면 false로 출력하므로 !을 통해 해결하였습니다.