[Python] 프로그래머스, 전화번호 목록 Lv.2 (feat.HashMap, 해시, startswith, 파이썬)

반짝반짝 알고리즘, 인프준

 

 

 

 

 

 

 

 

 

 

전화번호 목록

문제 링크

프로그래머스

 

 

문제 설명

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.

 

전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

 

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

 

입출력 예 설명

입출력 예#1

위 설명한 예시와 같습니다.

 

입출력 예#2

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

 

입출력 예#3

첫 번째 전화번호, "12"가 두 번째 전화번호 "123"의 접두사입니다. 따라서 답은 false입니다.

 

 

 

 

 

 

---

 

 

 

 

 

 

해결 과정

'전화번호 목록' 문제는 프로그래머스 > 코딩테스트 고득점 Kit > 해시에 속해있는 문제이기 때문에 해시를 활용하여 문제를 풀려고 접근했습니다. 전화번호부의 모든 번호를 Hashing 해두고 접두어를 확인하는 방식으로 구현해 보았습니다.

 

 

1. 파이썬 Dictionary는 HashMap을 구현할 수 있는 자료구조, 선언 후 모든 전화번호를 해시맵에 담아줍니다.

 

💡 HashMap

✓ Map의 특징인 Key-Value를 묶어 하나의 데이터로 저장
✓ Hashing(HashTable을 생성)을 사용하기 때문에 많은 양의 데이터를 검색하는데 강점
✓ Key는 중복 X, Value는 중복 O - 똑같은 Key에 입력 시 기존 Key-Value는 덮어씌워짐
✓ 순서를 보장하지 않음

 

 

2. 접두어를 하나씩 forloop으로 만들어서 hash_map에 존재하는지 확인해 줍니다.

 

3. 확인 중인 내 번호가 아니면서 해시 맵에 존재한다면 False를 반환, 모두 확인해도 없다면 True를 반환합니다.

 

 

 

제출 코드

def solution(phone_book):
    # 1.Hash map 생성
    hash_map = dict()
    for number in phone_book: 
        # 1개의 전화번호가 존재한다는 의미
        hash_map[number] = 1
        
    # 2.접두어가 Hash map에 존재하는지 찾기 
    for number in phone_book: 
        prefix = ""
        for num in number: 
            prefix += num
    
            # 3. 내 번호가 아니고, Hash map에 있다면
            if prefix != number and prefix in hash_map:
                return False
        
    return True

 

 

 

 

 

 

 

 

 

---

 

 

 

 

 

 

또 다른 풀이

 

def solution(phoneBook):
    phoneBook = sorted(phoneBook)

    for p1, p2 in zip(phoneBook, phoneBook[1:]):
        if p2.startswith(p1):
            return False
    return True

 

zip()과 startswith() 메서드를 사용해서 푼 깔끔한 코드입니다. 파이썬은 정말 쉽고 깔끔한 언어임을 다시 한번 느낀 문제였습니다.

 

# True
word = "Hello world"
print(word.startswith("Hello"))

# False
word = "Hello world"
print(word.startswith("hell"))

 

 

 

 

 

 

 

 

 

---

 

 

 

 

 

 

 

 

 

 

출처: 프로그래머스 코딩 테스트 연습,https://school.programmers.co.kr/learn/challenges