99클럽 코테 스터디 1일차 TIL + 프로그래머스/2/42577. 전화번호 목록/

# [level 2] 전화번호 목록 - 42577

[문제 링크](https://school.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

입출력 예 설명

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

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

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

---

알림

2021년 3월 4일, 테스트 케이스가 변경되었습니다. 이로 인해 이전에 통과하던 코드가 더 이상 통과하지 않을 수 있습니다.

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

코딩테스트 연습 | 프로그래머스 스쿨

 

 

<코드>

- 내가 시도 한 방법

def solution(phone_book):
    phone_book.sort()
    result = True
    
    # for phone in phone_book:
    #     for phone_v in phone_book:
    #         if (phone != phone_v) and (len(phone) < len(phone_v)):
    #             return phone_v.startswith(phone)
    
    for i in range(len(phone_book) - 1):
        if phone_book[i+1].startswith(phone_book[i]):
            return False            
                
    return result

문제점

1. 처음에는 정렬없이 이중 for문 안에서 if로 같은것은 바꾸는 방식으로 배열의 모든것을 순회하게끔 했음

2. 접두사에 대해서 정확히 처음에 이해를 못했음

 

배운점

1. startswith()라는 메소드를 알게 됨

- 이 경우에 startswith가 return 하는 bool과 실제 문제에서 요구하는 bool은 반대임

 

2. 비교는 정렬을 먼저하면 수월해짐

 

의문

1. 왜 옆에 있는 것만 확인해야하는지?

- 정렬을 하게 되면 접두사가 거의 비슷하기 때문임

"1195524421"와 "97674223" 비교 -> "97674223".startswith("1195524421") -> False

 

 

-모범사례

def solution(phone_book):
    answer = True
    hash_map = {}
    for phone_number in phone_book:
        hash_map[phone_number] = 1 #특별히 value이 필요가 없음
    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

일치하는지 한글자씩 확인하면서 늘려가기! -> 다만 리스트로 하면 안됨 (시간 복잡도가 늘어남)

 

해시에 key 가 있는지 확인은 해시 함수로 찾으려는 해시테이블의 Key 가 있는지로봄

 

해시는 O(1)임 일반 리스트접근때보다 시간 복잡도가 줄어듬

 

의문1 : 이게 왜 모범사례? 

의문2: 오히려 이중For문이 기 때문에 비효율적이지 않음?

 

<복습>

리스트와 해시의 시간복잡도 차이

 

리스트(동적배열)의 탐색은 O(n)

딕셔너리(해시)의 key를 이용한 탐색은 O(1)