프로그래머스 - 전화번호 목록(해시)

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	return
["119", "97674223", "1195524421"]	false
["123", "456", "789"]	true
["12", "123", "1235", "567", "88"]	false

 

# 풀이

- 파이썬의 내장함수인 접두어를 찾아주는 startswith()함수를 사용하여 문제를 해결해보았다.

def solution(phone_book):
    phone_book.sort()
    
    for i in range(len(phone_book)-1):
        for j in range(i+1, len(phone_book)):
            if phone_book[j].startswith(phone_book[i]):
                return False
                break
    return True

- 정확성 테스트에서는 만점을 받았지만 효율성 테스트에서 시간 초과 판정을 받았다.

- 아무래도 이중 for문을 사용해서 시간 복잡도가 늘어난 것으로 판단된다.

 

# zip()

- zip() 함수는 여러 개의 순회 가능한(iterable) 객체를 인자로 받고, 각 객체가 담고 있는 원소를 튜플(tuple)의 형태로 차례로

  접근할 수 있는 반복자(iterator)를 반환한다.

- 앞, 뒤 값을 비교하는 것을 이중 for문으로 인덱스 값을 받아서 처리하는 것이 아닌 zip()을 이용하여 해결할 수 있다.

lst = [12, 23, 22] # lst[1:] = [23, 22]

for l1, l2 in zip(lst, lst[1:]):
	print(p1, p2) # (12, 23), (23, 22)

 

# zip()을 이용한 풀이

def solution(phone_book):
    phone_book.sort()
    
    for p1, p2 in zip(phone_book, phone_book[1:]):
        if p2.startswith(p1):
            return False
            break
    return True

 

# 해시(hash)를 이용한 풀이

- 문제의 분류가 해시 문제이므로 해시를 이용한 풀이를 찾아보았다.

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:
                answer = False
    return answer

1. phone_book 리스트에 있는 숫자들을 딕셔너리로 만들어 준다.
2. 딕셔너리에 있는 숫자들을 하나씩 분해해보며 딕셔너리 키로 같지만 전체 숫자와 다른 경우 접두어가 존재하므로 False를 return한다.

- 딕셔너리를 탐색하는 경우 시간 복잡도가 O(1)로 줄어들기 때문에 시간 복잡도 문제를 해결할 수 있다고 한다.

 

 

# 고찰

• 매번 시간 복잡도에서 초과 판정을 받는데 이 부분을 해결할 수 있는 내장함수나 알고리즘을 익히는 것이 필요하다.
• 해시, 딕셔너리는 시간 복잡도를 해결해 줄 수 있으나 문제가 해시와 딕셔너리를 이용할 수 있는 문제인지 먼저 파악해야 할 것이다.