[프로그래머스-전화번호 목록(해시)-효율성 탈락]

코딩테스트를 공부해보려고 하루에 하나라도 풀어보자는 생각에 프로그래머스를 시작하게 되었다..첫번째 문제는 차질없이 테스트에 통과하였고 두번째 문제인 "전화번호 목록"이라는 문제를 풀었지만 효율성에서 탈락...

[문제 설명]

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

제한 사항

phone_book의 길이는 1 이상 1,000,000 이하입니다.
- 각 전화번호의 길이는 1 이상 20 이하입니다.
- 같은 전화번호가 중복해서 들어있지 않습니다.

해시를 활용하라는 문제였지만 결국엔 반복문을 돌린상황이라 이 사단이 낫나 싶었다...이전에는 됫었지만 테스트코드가 바뀌면서 효율성에 좀 더 신경을 쓴 문제가 된 것 같다.

열심히 두들이다가 나의 무지함을 깨닫고 결국 구글링을 시작하였고 해결방법을 찾아냈다

이 소스와 이전 문제의 소스의 큰 차이점이 무엇일까 생각해보면

나는 처음에 비교하려는 두개의 전화번호가 있다면 짧은 전화번호를 기준으로 긴 전화번호를 짦은 전화번호만큼 잘라내어 비교를 해야겠다고 생각했지만

해결 코드는 발상이 좀 달랐다..

전화번호중에 짧은 전화번호의 길이를 기준으로 긴 전화번호에서 나올 수 있는 접두어의 경우의 수들을 Set에 저장을 해두고 저장된 Set에서 짧은 걸 기준으로 검색을 하게하는것!

이렇게 된다면 이미 저장된 Set에 있는것만을 기준으로 검사하기도 해서 이전 방법처럼 일일히 잘라낼 필요가 없을 뿐더러 Set의 contains함수를 이용하여 검색성능도 올라가게 된다.

난 처음에 접두어만 찾아내는거니까 contains를 절대 쓰면 안되겠다고 판단했었다. 그러기에 해시를 활용할 생각자체를 안했던거 같다.

해결 소스의 자세한 설명을 하자면

접두어가 될 수 있는 문자를 저장하는 Set를 만들어 준다.
현재 전화번호 목록을 문자열 길이에 따라 길이가 긴 문자를 기준으로 Sorting한다.
현재 전화번호 목록에서 가장 짧은 문자의 길이(minLength)를 알아낸다.
전화번호 목록을 반복하면서 현재 set에 비교하려는 전화번호(number)가 포함되있는지 찾는다.
접두어가 겹치는 전화번호를 찾지 못했다면 현재 전화번호를 minLength를 시작으로 접두어가 될 수 있는 문자열을 만들어 낸 후 Set에 저장한다.
이 후 늘어나는 Set은 접두어가 될 수 있는 경우의 문자들이 저장될 것이며 생성도중 한번이라도 반복문의 현재 문자와 겹치게된다면(4번) false를 리턴하고 겹치는 접두어가 없다면 true를 리턴하여 결과를 도출한다.

위 성능 체크 비교 이미지를 보면 테스트 14 전 까지는 탈락소스가 빠르다가 후 부터는 엄청나게 느려지고 있는걸 확인할 수 있다. 테스트 코드가 뭔지 알 수가 없으니 답답할 나름이지만 탈락 소스는 데이터의 양이 많아지면 성능이 저하된다고 생각한다.