[level 2] 전화번호 목록

1. 문제

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

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

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

제한 사항

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

 

---

 

2. 문제 풀이

 

문제 풀이 접근법1

1) 접두어에 해당하는 phone_book[0]을 prefix 변수에 저장한다.

2) 배열 슬라이싱을 사용하여 phone_book[i][0: len(prefix)] 의 값이 prefix와 일치하는지 확인한다.

3) 만약 일치한다면, True를 False로 변경한다. 

def solution(phone_book):
    answer = True
    
    prefix = phone_book[0]
    
    for i in range(1, len(phone_book)):
        if phone_book[i][0:len(prefix)] == prefix:
            answer = False
        
    return answer

테스트 케이스는 다 맞았고

실제 체점에서는 정확도 45.8, 효율성 4.2가 나왔다. 

(정확성 8, 9, 12, 15, 19 실패 / 효율성 1, 2, 4 실패 )

 

✏️내가 잘못 생각했던 부분 

나는 처음에 오는 단어가 무조건 접두어가 되는 거라고 생각을 했었는데,  생각을 해보니까 그냥 i번째 전화번호가 j번째 전화번호의 접두어가 되면 되는 거였다! 

+) '숫자 문자열'을 sort할 경우, 해당 문자열의 첫번째 인덱스 문자를 기준으로 sorting 한다고 한다. 

ex)  [ '1117', '23', '12345', '3' ]을 sorting 하면 [ 1117', '12345', '23', '3' ] 으로 sorting 됨 

 

따라서, 먼저 sorting을 하면 가장 작은 단어가 앞에 가게 될 것이고, 해당 단어와 가까운 단어들로 sorting이 된다는 장점이 존하게 된다! 

즉, 자신의 옆만 생각하면 된다 (우측 옆이 자신과 가장 가까운 단어가 되므로) 

 

 

문제 풀이 접근법2

1) phone_book을 sorting한다

2) i번째 phone_book과 i+1번째 phone_book의 lne(phon_book[i]) 만큼을 비교한다.

3) 만약 맞다면 answer를 False로 변경하고 break문을 통해 빠져 나온다.

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][0: len(phone_book[i])]:
            answer = False
            break 
        
    return answer

 

 

---

 

 

 

3. 다른 분들 문제 풀이 

 

1) startswith 함수 이용 

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

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

보자마자 헉 했다. 

zip으로 문제를 풀 생각은 전혀 못했고 startswith함수 있는지도 몰랐음 

startswith() 함수는 현재 문자열이 사용자가 지정하는 특정 문자로 시작하는 지를 확인하는 함수라고 한다. 

비슷한 함수로 endswith()함수가 있다. 

참고로 return 값은 True/False이다. 

https://leftday.tistory.com/102

python 문자열 시작과 끝 문자 찾기, 접두사 startswith, 접미사 endswith

 

 

2) 해시 테이블 이용 

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

 

3번째 줄: hash_map을 초기화한다.

4~5번째 줄: phone_book의 원소들로 hash_map을 만든다. 여기서 만들게 되는 hash_map은 다음과 같다. 

hash_map = {
    "119": 1,
    "97674223": 1,
    "1195524421": 1
}

 

6번째 ~ 11번째 줄: phone_book의 원소를 차례대로 이용하면서 for문을 돌린다.

• 7번째 줄: 새로운 원소로 phone_number가 갱신될 때 마다 temp를 초기화한다. 
• 8번째 ~ 11번째 줄: phone_number, 즉 phone_book 리스트에 있는 원소로 for문을 돌린다
  • 9번째 줄: 차례대로 phoce_number의 원소를 temp에 더해가며 부분 문자열 temp를 만든다.
  • 10번째 줄: 만약 temp가 hash_map 안에 있고, 해당 문자열이 phone_number가 아니라면(즉, 본인이 아니라면) answer를 False로 만든다. 

 

 

4. 배운 것 

숫자 문자열을 sorting 하면 첫번째 인덱스를 기준으로 sorting 됨!

가장 자신의 우측에 존재하는 문자열을 자신과 가장 비슷한 문자열

 

참고: https://copro505.tistory.com/entry/%EC%A0%84%ED%99%94%EB%B2%88%ED%98%B8-%EB%AA%A9%EB%A1%9D

전화번호 목록 →기준값 갱신+startswith()+숫자문자열 정렬★★