프로그래머스 고득점 kit(유형정리) - 전화번호 목록

코딩테스트 연습 - 전화번호 목록 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

문제 설명

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

• 구조대 : 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

입출력 예 설명

입출력 예 #1
앞에서 설명한 예와 같습니다.

입출력 예 #2
한 번호가 다른 번호의 접두사인 경우가 없으므로, 답은 true입니다.

입출력 예 #3
첫 번째 전화번호, “12”가 두 번째 전화번호 “123”의 접두사입니다. 따라서 답은 false입니다.

 

 

※ 알고리즘

1. phone_book 배열을 sorting 한다.

2. i와 j를 zip을 사용하여 for문으로 phone_book 인덱스와 phone_book의 다음 인덱스를 조사한다.

3. startswith를 사용하여 i와 j를 조사하여 같은 전화번호가 접두어로 중복되면 false를 반환, 아니면 true를 반환한다.

 

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

 

이렇게 간단하게 startswith와 endswith 메서드만 알고 있으면 정말 쉽게 해결이 가능하다. 하지만, 이 문제는 Hash문제 이므로 hashmap을 사용하여 풀이한 다른 사람의 풀이를 소개하겠다.

 

<HashMap을 사용한 풀이>

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

 

자바와는 다르게 파이썬은 hash map이 dictionary라는 문법으로 애초에 사용할 수 있게 되어 있다. Key와 Value를 사용하여 dictionary 형식으로 문자를 비교할 수 있다. 

hash_map[phone_number] = 1은 첫번째 key를 1로 담아둔 것으로 예상된다. phone_number 안에서 number를 찾게 되면 temp변수에 담고 이를 phone_book 에서 비교하는 형식이다. 만약 hash map 안에서 temp 변수를 찾을 수 있고, phone_number 안에서 temp변수가 찾아지지 못하게 되면 접두어가 포함되어 있는 상태가 되므로 False를 반환하고 아니면 True를 반환한다.

 

python에서는 딕셔너리 문법을 사용하여 hash_map을 자바와는 다르게 편하게 사용할 수 있다.