[Algorithm] Programmers 전화번호 목록 Python 풀이

 

1. 문제

전화번호 목록

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

 

• 전화번호 목록의 배열이 입력으로 주어진다.
• 전화번호 중에서 한 전화번호 전체를 접두어로 하는 다른 전화번호가 있는지 찾는다.
• 접두어로 하는 다른 전화번호가 있다면, false를 return한다.
• 접두어로 하는 다른 전화번호가 없다면, true를 return한다.
• 전화번호 목록 내에서 같은 전화번호가 중복해서 들어있지 않다.

 

2. 풀이

• 해쉬(Hash) 문제이므로, 해쉬 개념을 사용해야 할 것 같다.
• 물론 해쉬를 사용하지 않고도 풀 수 있는 방법은 있다.
• 해쉬란? 데이터를 다루는 기법 중 하나로, 검색과 저장을 빠르게하는 자료구조이다. 해쉬 개념 관련 포스팅은 여기
• 해쉬는 데이터를 저장할 때 Key-Value 형태로 데이터가 존재한다.
  • Key 값이 배열의 인덱스로 저장된다. 따라서 검색과 저장이 빨라질 수 있다. 
• 해쉬 개념을 사용하여, Key(접두어)로 Value(전화번호)를 매칭하여 검사

 

정답 코드의 idea

 

• Dictionary 변수의 Key에는 전화번호를 저장하고, Value에는 1을 저장하여 초기화한다.
  
  •  근데 풀어보니까 Dictionary 변수가 아니라 그냥 List를 만들어서 풀어도 되는 것 같았다.
  • 그치만 List보다 Dictionary로 검사하는게 더 빠르다고 한다.
• 이중 For 문으로 전화번호 내의 전화번호를 번호 하나하나씩 비교하여 접두어가 있는지 확인한다.
• 접두어가 있는지 확인할 때는 Dictinoary 변수의 Key로 찾는다.
• 접두어가 있는지 확인할 때 접두어 전화번호를 한 변수에 확인용으로 만들고, 전화 번호 부 내에서의 접두어 전화번호도 확인해버려서 False를 return하지 않도록 조심해야 한다.
  • 접두어 전화 번호 본인은 같은지 확인할 필요가 없다는 말

 

3. 전체 코드

def solution(phone_book):
	answer = True
    hash_map = {}
    
    for phone_number in phone_book:
    	hash_map[phone_number] = 1
        
    for phone_number in phone_book:
    	temp = "" #접두어를 다른 전화 번호와 비교하기 위한 변수
        for number in phone_number: #전화 번호 부 내의 전화 번호를 번호 하나하나씩 비교
        	temp += number
            if temp in hash_map and temp != phone_number: #전화 번호 Hash map의 Key에 접두어가 있는지 확인, 접두어 본인은 빼고 검사
            	return False
                
	return answer

 

 

(이 아래는 사족)

Problem Solving 하면 깃허브에 올려두기는 하는데, 답만 올려두니 며칠 뒤면 잘 까먹는 것 같았다. 그래서 지금부터라도 블로그에 알고리즘 문제 풀이를 정리해보았다.

 

사실 처음에 풀 때는 해쉬를 사용하지 않고 풀었다.

그런데 해쉬 문제인 만큼 정석으로 풀 필요가 있다고 생각되었다.

그래야 다른 해쉬 문제들도 풀 수 있을 것 같았다.

 

해쉬를 사용해서 문제를 어떻게 풀었는지, 다른 분들의 코드를 참고하였다.

구글에도 많이 나오고, 프로그래머스 내에서도 많은 분들이 해쉬를 이용해서 푼 것이 나온다.

 

해쉬를 사용하지 않고 풀어도 되지만,

해쉬 자료구조에 대해서 미리 공부를 해놓으면 이 개념을 사용해서 다른 해쉬 문제들도 풀 수 있다.

따라서 해쉬에 대해서 미리 공부할 필요가 있는 것 같다.

 

해쉬 테이블 자료 구조에 대해서 자세히 공부하고 싶다면, 아래 유튜브 영상이 도움이 될 것 같다.

설명을 이해하기 쉽게 잘 해주셔서 자료 구조에 대해서 잘 몰라도 개념을 쉽게 익힐 수 있도록 도와주신다!

 

[자료구조 알고리즘] 해쉬테이블(Hash Table)에 대해 알아보고 구현하기

 

참조

• 개발자로 취직하기