[프로그래머스] Level2 | 전화번호 목록 - 파이썬(Python) | 해시(Hash)

https://programmers.co.kr/learn/courses/30/lessons/42577

코딩테스트 연습 - 전화번호 목록

---

정말 이해가 안되는 문제였다!! 문제가 이해가 안되는게 아니고 내가 푼 풀이는 왜 통과가 안되는지?가 의문인 문제이다 ㅋㅋㅋㅋ...

 

해시 문제라고 되어있지만 나는 해시를 이용하지 않고 풀었다.

 

첫번째 시도 - 테스트 케이스 왕창 틀림, 효율성 2/4 틀림

def solution(phone_book):
    answer = True    
    
    phone_book = sorted(phone_book)
    book_list = phone_book[1:]
    
    for i in range(len(book_list)) :
        if phone_book[0] in book_list[i] :
            phone_book.remove(phone_book[i+1])   
            
    if len(phone_book) != len(book_list) +1 :
        answer = False
        
    return answer

2중 for문을 사용하지 않으려고 sorted를 사용하여 정렬을 했다.

정렬했을 때 가장 짧은 길이의 문자를 접두어로 생각하고 phone_number[0]가 book_list의 원소들에 포함되면 그 원소는 제거하는 형식으로 진행했는데 테스트 케이스에서 왕창 틀렸다.

잘못된 접근법이라 생각하고 다른 방법으로 시도했다.

 

두번째 시도 - 테스트 케이스 2개 틀림, 효율성 1/4 틀림

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

phone_book[0]으로 시작하는 문자이면 true를 반환하는 startswith 함수를 사용했다.

startswith가 True이면 answr는 False이고 for문이 종료되도록 했다.

분명 문제가 될 것 없어보였는데 이상하게도 테스트 케이스 2개가 틀리고 효율성도 1개가 틀렸다.

 

대체 얼마나 더 개선을 해야하나.. 하고 다른 사람들의 풀이를 찾아보았다.

 

다른 사람들 풀이 - 세번째 시도

def solution(phone_book):
    answer = True    
    
    phone_book = sorted(phone_book)
    
    for i, j in zip(phone_book, phone_book[1:]) :
        if j.startswith(i) :
            answer = False
        
    return answer

zip을 이용해서 phone_book과 phone_book[0]을 제외한 list의 원소들을 1:1로 매칭을 시켰다.

이때 phone_book[0]을 제외한 list가 phone_book으로 시작하면 answer는 False가 되도록 했다.

 

break를 걸지도 않았는데 효율성도 모두 통과되었으며 테스트 케이스도 모두 통과되었다...

대체.. 무슨차이일까...?

 

---

해당 문제 풀이 코드

GitHub - YOOHYOJEONG/algorithm_practice: 알고리즘 공부 및 코딩테스트 준비