0926_프로그래머스 #42577. 전화번호 목록

문제

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

프로그래머스

---

코드

1. deque()을 활용한 코드 -> 오답

from collections import deque

def solution(phone_book):
    answer = True
    flag = 0
    phone_book = deque(sorted(phone_book, key=lambda x:len(x)))
    for i in range(len(phone_book) - 1):
        
        if flag == 1:
            break
            
        phone = phone_book.popleft()
        l = len(phone)
        for num in phone_book:
            if phone == num[:l]:
                answer = False
                flag = 1
                break
            
    return answer

 

※ 이 코드로도 테스트 케이스는 모두 맞았고, 히든 테스트 케이스에도 걸리지 않았다! 다만, 이 문제는 효율성 테스트도 있었는데 4문제 중 2문제에서 시간 초과가 나서 틀렸다 ㅜㅠ 아무래도 for문을 2번 쓰다보니 시간 복잡도가 증가한 것 같다! 그리고 항상 문제를 풀면서 느끼는 점인데 나는 deque()를 너무 좋아하는듯 ..

 

2. sort()를 활용한 코드 -> 정답!

def solution(phone_book):
    answer = True
    phone_book.sort()
    for i in range(len(phone_book) - 1):
        num = phone_book[i]
        if phone_book[i + 1].startswith(num):
            answer = False
            break
            
    return answer

 

※ 훨씬 더 간결해진 코드! 정렬 기준을 문자열의 길이가 아닌 단순 정렬로 바꾸었다. 이 부분에서 아래 블로그를 참고했다. 정말 설명을 잘해주셔서 이해가 잘되었당 ㅎㅎ 그리고 startswith()이라는 함수도 처음 사용해보게 되었다. 알고리즘을 풀다보면 다들 구현 과정 생각을 너무 잘해서 놀랍다 .. 나도 그런 창의적인 생각을 하는 머리를 갖고 싶다 ..

 

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