[프로그래머스] 전화번호 목록 (정렬보다는 해시를)

문제: https://programmers.co.kr/learn/courses/30/lessons/42577?language=python3

코딩테스트 연습 - 전화번호 목록

 

정렬을 이용하는 방법

사실 보자마자 딱 생각나는 방법은 정렬하고 두 개씩 비교하는 방법입니다.

 

정렬하면 앞부분이 비슷한 것들끼리 인접하게 되기 때문에 인접한 두 전화번호끼리만 비교해도 결과는 맞게 나옵니다.

 

 

효율성 테스트도 나쁘지 않게 나오네요.

 

해시로 풀어보기

그래도 해시 관련 문제이므로 해시로 다시 풀어봤습니다.

 

접두사가 될 수 있는 것들을 모두 해시맵에 저장하고,

 

전화번호 목록을 돌면서 해시맵에 있는 번호와 일치하는 게 있는지 검사합니다.

 

 

효율성 테스트를 보면 정렬을 이용한 게 수십배씩 더 빨라서 정렬이 더 좋지 않나하는 생각이 들 수도 있습니다.

 

이 문제에 대해서는 그럴 수도 있겠지만, 만약 전화번호가 추가된다면 그때마다 정렬을 다시 해야하기 때문에

 

현실적인 풀이는 해시를 이용한 방법이라고 생각합니다.