[프로그래머스/Python] 해시 - 전화번호 목록

전화번호 목록

---

문제 설명

---

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

• 구조대 : 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입니다.

 

---

나의 풀이

def solution(phone_book):
    phone_book.sort() # 문자 정렬은 ["119", "1195524421", "97674223"]와 같이 숫자 크기대로 되는 것이 아님.

    for i in range(len(phone_book)):
        if i == len(phone_book)-1:
            break

        # 정렬을 했기 때문에 두 글자만 비교함
        prefix = phone_book[i]
        other_num = phone_book[i+1]

        # 접두어가 비교하는 전화번호 맨 앞에 존재할 때
        if prefix in other_num and other_num.index(prefix) == 0:
            return False

    return True

- 💡 아이디어
먼저 파이썬 내장 라이브러리를 이용하여 전화번호부를 정렬해준다. 
숫자를 정렬하면 숫자의 크기순대로 정렬되지만, 문자로 정렬하면 ["119", "1195524421", "97674223"]와같이 정렬된다.
따라서 연속되는 두 글자만 비교하면된다. 이는 for문을 사용해서 비교해주었다.

각각 변수명은 prefix와 other_num이라 설정해주었다. prefix가 other_num에 존재하고, prefix가 접두어가 맞다면(index(prefix) == 0)이라면 False를 출력하도록 했다.  

- 📚 후기
처음엔 이중 for문을 쓰도록 했다. for문 하나는 prefix를 설정해주는 데 사용하였고, 다른 for문을 통해 prefix와 나머지 리스트 내의 모든 전화번호와 비교하였다.

이렇게 하니 정확성 테스트는 모두 통과하였지만, 효율성테스트에 3,4번 문제에서 계속 시관초과가 떴다.

문자를 정렬하면 저런식으로 정렬이 되는지 몰랐다. 정렬을 사용한 후 앞 뒤 두 글자만 비교하도록 설정했더니 효율성문제가 해결되었다.

- ✏️ 배운점
  1. 문자열을 정렬하면 숫자 순서대로 정렬되는 게 아니라는 것.
  2. startswith 함수 : 원본 문자열이 매개변수로 입력한 문자로 시작되는지 판단하는 함수(대소문자 구분함) (endswith함수도 있음)
  3. 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