프로그래머스 해시 level2 전회번호 목록

문제 설명

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

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

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

 

아이디어

도전2

1. sort하기

2. 문자열로 바꾸기 -> 숫자도 if in 사용 가능

3. for로 비교

- 비교 대상이 자신의 다음 것부터 마지막까지 비교

- 하나라도 겹치는 것이 있다면 true 반환

=> 이렇게 할 경우 폰 북이 엄청 길 경우에  폰 북 길이의 !팩토리얼 만큼의 시간복잡도가...

 

def solution(phone_book):
    phone_book.sort() 
   
    for n in range(len(phone_book)):
        for vs in range(n+1,len(phone_book)):
            if phone_book[n] in phone_book[vs]:
                return False
    return True    

 

 

통과 (3.29ms, 15.3MB)

phone_book.sort()을 안하면 테스트 케이스가 실패하곤 하는데,,, 왜 그런거지?

잘못된 아이디어 모음

- 처음부터 비교하여 하나라도 같으면 true

- 아니면 false

 

1.  for문을 통해 phone_book에 첫번째 원소의 첫번째 값과 다른 값들의 첫번째\원소와 비교

2. 다르면 멈추고 다음 것과 확인

3. 같으면 바로 true 반환

4. 다 돌았는데도 없으면 false 반환

=> 하나라도 같으면 되는거니까!

=> 그런데 이렇게 할 경우 폰 북이 엄청 길 경우에  폰 북 길이의 !팩토리얼 만큼의 시간복잡도가...

 

 

1. phonebook에 있는 첫번째 원소들의 개수를 카운팅하여 1이상인 값이 있으면 true!

 

from collections import Counter

def solution(phonebook): 
    phonebook = list(map(str, phonebook))

    firstphone = [phonebook[i][0] 

for i in range(len(phonebook))] 
    dict_phone = Counter(firstphone) 
    print(dict_phone)

for i in dict_phone.values():

    if i >= 2: 
            return False 
    return True

 

========

정확성: 46.2

효율성: 15.4

합계: 61.5 / 100.0

 

==> 애초에 문제를 제대로 못 읽은 것이 한 번호!!가 어떤 번호의 접두어인경우임!

 

 

기타 풀이

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

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

 

 

통과 (3.35ms, 15.3MB)

 

1. zip을 이용하여 [phonBook[n],phonBook[n+1]]로 묶어준다.

- zip()은 내장함수로 같은 길이의 리스트를 같은 인덱스끼리 잘라서 리스트로 반환해주는 역할을 한다.

- startswith 는 특정문자열을 찾아 ture, false를 반환하는 메소드이다.

  str1.startswith(str2,시작, 끝)과 같은 형태로 사용되어집니다.

 

=> 정렬되어진 상태이기 때문에 앞뒤만 비교해도 접두어를 찾을 수 있나보다...?

 

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

통과 (14.96ms, 15.3MB)

1. 딕셔너리 형태로 만들어준다. => 이렇게 해야 나중에 찾을 때, 리스트에 비해 찾는 속도가 빠르기 때문인가보다.

2. 번호를 하나씩 가져와서, 

하나씩 만들어주며 비교해본다.