[프로그래머스] 전화번호 목록

프로그래머스 코딩테스트 고득점 KIT 중 해시 카테고리에 있는 문제입니다.

• 난이도 Level 2

문제 링크입니다.
https://school.programmers.co.kr/learn/courses/30/lessons/42577

문제 풀이

---

풀이를 떠올리는 단계까지는 수월했습니다.

처음에는 가장 길이가 짧은 번호를 뽑아서 다른 번호의 접두사인지 확인해볼까? 로 접근했습니다.

min_num = min(phone_book, key = lambda x: len(x))

하지만, 쉽게 알 수 있듯이 가장 짧은 길이의 번호만 접두사가 되진 않으니 많은 예외상황이 존재합니다.


그래서 phone_book 배열을 순회하면서 서로서로 비교해야 할 까? 로 접근했습니다.
하지만, 배열의 크기가 1,000,000 이라서 이중 for문을 돌면 무조건 효율성은 실패하겠다는 생각이 들었습니다.

곰곰히 생각해보니 '접두사'를 비교하면 되니 문자열의 특징을 고려하면 되겠구나! 라는 생각에
문자열을 정렬하는 단계까지 도달했습니다.
(이전에 문자열 정렬을 하면 얻는 이점을 문제를 통해서 습득했기 때문에 활용할 수 있었습니다.)

>> phone_book = ['934793', '34', '44', '9347']
sorted_book = sorted(phone_book)
>> sorted_book = ['34', '44', '9347', '934793']

이렇게 정렬되면 더 쉽게 접두사를 비교할 수 있습니다.

 

반복되는 실수

---

실컷 정렬해놓고 이상한 코드를 짰습니다. 정확성 테스트는 통과했지만 효율성 2문제는 시간초과가 떴습니다.

바로 이중 for문을 짠 것입니다.🥲

슬라이딩 윈도우 처럼 바로 다음 단어와 비교하는 것을 모든 원소에 대해서 동작하도록 짜버렸습니다.
어차피 정렬 뒤라 모두 반복할 필요가 없는데요...!

그래서 for 문 한 개를 없애고 다시 구현하니 효율성 테스트를 통과할 수 있었습니다.
이런 실수가 반복되는 것은 실력이라고... 좀 더 정확하고 꼼꼼하게 문제 푸는 연습을 해야겠습니다.

정답

"""
접두어인 경우가 있으면, False
아니면, True
"""

def solution(phone_book):
    sorted_book = sorted(phone_book)
    for i in range(0, len(sorted_book)-1):
        length = len(sorted_book[i])
        if sorted_book[i] in sorted_book[i+1][:length]:
            return False
    return True