[프로그래머스] Lv2. 전화번호 목록(Python 풀이/해시)

문제 설명

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

• 구조대 : 119
• 박준영 : 97 674 223
• 지영석 : 11 9552 4421

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

 

제한 사항

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

입출력 예제

phone_bookreturn

["119", "97674223", "1195524421"]	false
["123","456","789"]	true
["12","123","1235","567","88"]	false

 

문제 접근

간단하게 생각해서 이중 for문을 이용해서 각 문자열이 서로 접두어인지 판단하면 된다고 생각해서 아래와 같이 접근해서 풀었다.

 

1. 첫번째 풀이

 

효율성은 이중 for문을 사용해서 통과하지 못할 것 같다는 생각도 들었는데 정확성 테스트에서 왜? 계속 실패가 뜨는건지 사실 잘 이해가 안됐다. 실패 케이스를 찾던 중 생각해보니까 내가 접두어라는 말을 제대로 이해하지 못하고 그냥 다른 문자열에 이 문자열이 포함되기만 하면 되는거지라고 생각하고 진행해서 틀렸었다. 그래서 아래와 같이 변경해서 다시 작성해보았다.

 

2. 두번째 풀이

 

정확성은 성공했지만 효율성은 실패했다. 첫번째 코드에서 정확성이 실패한 이유는 문자열을 모두 포함해서 비교하는 식을 짰기 때문이다. 접두어는 어떤 단어의 앞에 붙어 뜻을 첨가하여 하나의 다른 단어를 이루는 말로 "119"과 "1195524421"를 비교했을 때 "1195524421" 앞의 3글자가 119로 시작하기 때문에 단어의 앞에 붙는게 맞지만 내가 짠 코드는 "119"와 "5524421119"를 비교했을 때 119가 뒤에 붙어 있더라도 식이 True로 동작했기 때문이다. 하여 Python의 startwith()함수를 이용해서 앞에서부터 문자열을 비교하여 포함하는게 있는지 접두어를 체크해서 식을 풀어냈다. 하지만 이것도 효율성에선 완전 꽝이기 때문에 조금 더 빠르게 검색할 수 있는 해시를 이용해보았다.

 

3. 세번째 풀이

 

위는 해시 테이블로 풀었다. 해시는 간단하게 얘기하면 Key와 Value로 이루어진 자료구조로 연산의 시간복잡도가 O(1)로 빠르게 값을 찾아낼 수 있다.

hash = {
	'119' : 1,
    '97674223' : 1,
    '1195524421' : 1
}

 

 

우선 해시 테이블에 위와 같이 저장한 후 phone_num안에 있는 값들을 빼내고 빼낸 값들의 문자열 하나하나를 빼내어 temp에 저장하여 저장된 temp의 값이 hash안에 있는지 비교한다.

 

예를 들면 "1195524421" 값이 phone_num에서 빠지고 "1195524421" 값의 첫번째 문자인 '1'부터 temp에 저장시킨다. temp에 저장된 "1"은 당연히 해시 테이블 안에 없기에 다시 넘어가서 temp가 "11"이 되고 "11"도 해시 테이블안에 없는 수이기에 temp가 "119"가 된다. temp가 "119"가 되면 해시 테이블 안에 값이 있어 1이되고 num인 "1195524421" 과 temp를 비교했을 때 다르기 때문에 if 문의 조건이 성립되어 접두어인 것을 확인할 수 있다.

 

확실히 일일이 비교하는 것보다는 해시를 활용한 검색이 훨씬 빠른 것 같다. 시간 날때 해시에 대해 조금 더 검색해보고 기술해보아야겠다!