[ 프로그래머스 ] 전화번호 목록 _ Hash

[ 문제 분류 ]

- Hash

 

[ 문제 링크 ]

- https://school.programmers.co.kr/learn/courses/30/lessons/42577

프로그래머스

 

[ 문제 설명 ]

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

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

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

 

** 제한 사항 **

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

** 입출력 예제 **

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

 

[ 문제 풀이 ]

• 문자를 기준으로 정렬하여 앞 뒤 연속되는 두 글자만 비교할 수 있도록 한다! 
  • 1번 예시를 문자를 기준으로 정렬하면 [ '119', '1195524421', '97674223'] 가 된다. 
    즉, 숫자 크기로 되는 것이 아니라 문자의 '앞'부분이 작은 숫자부터 정렬된다. -> 이렇게 되면 비슷한 문자가 앞뒤로 정렬되기 때문에 연속되는 두 글자만 비교해서 문제 풀이 가능!
• 비교하는 두 문자에서 뒷 문자에 앞 문자가 들어있는지 확인하고 있다면 False를 리턴!
• 해시 함수를 이용할 경우, 목록에 있는 전화번호를 다 넣고 각 키값의 문자들을 하나씩 쪼개어 비교 -> 풀이코드 2번 참고
• 풀이 방식은 다양함 -> 이중 for문을 사용할 수도 ( 시간 고려 필요 ), startswith함수, hash 사용 등등

 

[ 문제 풀이 코드 ]

def solution(phone_book):
    answer = True
    phone_book.sort() # 숫자 크기대로 정렬되는 것이 아님! 문자 앞부분부터 보면서 작은 순서대로!
    for i in range(len(phone_book)-1):
        if phone_book[i] < phone_book[i+1]:
            if phone_book[i+1][:(len(phone_book[i]))] == phone_book[i]:
                return False
    return answer

 

# 해시를 사용한 풀이 
def solution(phone_book):
    answer = True
    dic = {}
    for k in phone_book: # 목록에 있는 전화번호를 모두 dic에 저장
        dic[k] = 1
    for number in phone_book: # 목록에 있는 하나를 꺼냄
        temp =''
        for num in number: # 꺼낸 하나를 문자 하나씩 쪼개서 temp에 하나씩 붙여나감
            temp += num
            if temp in dic and temp != number: # temp값이 다른애의 접두어에 해당하는 지 확인
                answer = False
    return answer

 

# 파이썬 내장함수 startswith 사용
def solution(phoneBook):
    phoneBook = sorted(phoneBook)
    for p1, p2 in zip(phoneBook, phoneBook[1:]): # zip -> sort 되어있기에 연속되는 두 글자가 비교될 수 있도록
        if p2.startswith(p1):# 내장함수 사용
            return False
    return True

 

[ 추가 정리 ]

* 파이썬 zip 함수 *

- zip() 함수는 동일한 개수로 이루어진 자료형을 묶어주는 역할을 한다. 

- 제너레이터로 리턴되기 때문에 list 나 dict 등으로 변환해 주어야 한다. 

- 두 자료형의 개수가 다를 경우, 긴 것의 남은 것은 누락된다.

list1 = [1,2,3]
list2 = ["홍길동", "김철수", "박미애"] 
zip_list = zip(list1, list2) 
print(zip_list, type(zip_list)) # 제너레이터로 리턴 <zip object at 0x1004b3b40> <class 'zip'>
print(list(zip_list)) # 리스트로 변환 [(1, '홍길동'), (2, '김철수'), (3, '박미애')]

# dictionary로 변환
dic ={} 
for i, s in zip(list1, list2):    
	dic[i] = s print(dic)

- 해당 문제의 1번 예시로 보면, 먼저 phone_book이 정렬되어 값이 [ '119', '1195524421', '97674223'] 가 된다

- 이를 zip(phone_book, phone_book[1:])을 하면 [('119', '1195524421'), ('1195524421', '97674223')] 가 된다. 

- 이에 for 문에서 앞 뒤 문자를 비교할 수 있는 것이다!

 

* 문자열 중 특정 문자를 찾을 때 쓰는 함수  *

1. find( 찾을 문자, 찾기 시작할 위치)

s = '가나다라 마바사아 자차카타 파하'
s.find('마') # 5

s.find('가') # 0
0

s.find('가',5)#-1 -> 없으면 -1 리턴

 

2. startswith( 시작하는 문자, 시작지점 ) -> 특정 문자로 시작하는지 확인 , 리턴값은 ture, false

s = '가나다라 마바사아 자차카타 파하'
s.startswith('가') # True

s.startswith('마') # False


s.startswith('마',s.find('마')) #True, find는 '마' 의 시작지점을 알려줌 : 5

s.startswith('마',1) # False

 

3. endswith( 끝나는 문자, 문자열의 시작, 문자열의 끝 ) -> 특정 문자로 끝나는 지 확인, 리턴값은 true, false

s = '가나다라 마바사아 자차카타 파하'

s.endswith('마') #False

s.endswith('하') #True

s.endswith('마',0,10) #False

s.endswith('마',0,6) #True

 

---