[해시] 전화번호 목록 lv.2

📌 문제

• 위와 같이 각 사람당 하나의 번호를 갖고 있다고 가정하자.
• 구조대의 번호는 지영석 번호의 앞자리 3자리와 같다.
• 이와 같은 상황에서, 구조대는 지영석 번호의 접두어이다.
• 접두어가 있는 경우 false, 없는 경우 true를 return 하라.

📌 풀이

🔥 생각1 - 완탐 ( Fail )

brute force로 풀 수 있는가?

 

for loop를 2번 돌면서, 완탐을 해보자.

효율성에서 걸린다.

N^2은 안된다.

좀 더 효율적인 방법을 생각해보자.

🔥 생각 2 - 아이디어

문제의 상황을 잘 들여다봐 보자.

어떤 수가 다른 수의 접두사가 되려면, 정렬했을 때 해당 수보다 무조건 앞에 있어야 한다.

 

ex) 123 1235 1234533539 ...

 

그래서 정렬 후에, for loop을 돌면서 해당 수가 다음 수에 대해 접두사를 만족시키는 지 확인해준다.

 

그러면 여기서 의문점이 들 수 있다.

 

124 1254 12479 처럼 124 1254 는 접두사 관계를 만족하지 않지만, 하나 건너 뛰어서 124 12479는 접두사 관계를 만족하지 않는가?

그런데, 정렬을 했으면 애초에 124 12479 1254로 정렬이 된다.

앞에서 접두사 관계를 만족하지 않으면, 뒤에서도 만족하지 않는 것이다.

 

이 때 주의할 점이 하나 있는데, 정렬을 하면 사전식으로 정렬이 된다는 것이다.

즉, 191 > 12234232 이다.

그래서 loop를 돌 때, 앞의 길이와 뒤의 길이를 비교해주어야 한다.

📌 다른사람 풀이

이 문제는 문제 자체가 쉬우므로, 최적화를 어떻게 해줄 것인가에 대한 문제라고 볼 수 있다.

 

아이디어는 다음과 같다.

접두사를 찾는다 : 빠른 검색 -> 해시

 

해시의 모집단을 설정해주어야 한다.

 

주어진 배열값인 phone_book 의 값을 hash에 집어넣자. value에는 해당 값의 index를 넣어준다.

그 다음, for loop을 돌면서 phone_book의 값을 1글자~ 해당글자의 길이 만큼 parsing한다.

 

예를 들면 123 4445 12345 가 있다고 하면

 

i=0

  1, 12 ,123<-- 이 값이 map의 key에 포함돼있는지 확인

 

만약 포함돼있으면, 해당 map의 value가 i와 같지 않다면 return false

 

loop를 빠져나왔다면 return true

https://coding-grandpa.tistory.com/77