[프로그래머스] 전화번호 목록(LV2 - Python)

프로그래머쓱

해당 글에서는 전화번호 목록 문제를 Python을 이용해 풀이하고자 한다.

프로그래머스

 

매일 1시간씩 코딩테스트 문제를 풀고 있는데, 빠르게 풀이하고 15분 정도가 남아 글을 작성하게 됐다.

이 문제를 선택한 이유도 새로운 아이디어를 얻어서 오래 기억하고자 기록한다.

 

🔷 문제 설명

귀찮으니 사진으로 대체...

 

🔷 문제 풀이

1️⃣ 첫 번째 풀이

첫 풀이는 단순하다. 그냥 딕셔너리에 모든 번호를 넣어두고, 각각의 번호를 0부터 n-1까지 슬라이싱하여 딕셔너리에 슬라이싱한 번호가 있으면 false를 반환해주면 된다고 생각했다.

 

phone_book의 최대 길이가 1,000,000이고, 각 전화번호의 길이의 최대도 20이기 때문에, 접두사가 있는지 확인하는 과정에서 최악의 경우더라도 2,000,000만큼의 연산이 일어난다고 생각해서 시간초과가 발생할 것이라 생각하지 않았다.

def solution(phone_book):
    answer = True
    
    nums = {} # dictionary
    for num in phone_book:
        nums[num] = True
    
    for num in phone_book:
        for i in range(1, len(num)):
            if nums.get(num[:i]):
                return False
    
    return True

 

위에서 연산이 2,000,000라고 생각했지만, 추가로 GPT에게 물어보니 잘못된 사실이라는 것을 깨달았다.

알고보니 문자열 슬라이싱 과정에서 슬라이싱 길이에 따라 시간을 더 많이 소모한다고 한다. 나는 이 부분을 고려하지 못했다.

 

 

2️⃣ 두 번째 풀이

두 번째 풀이 때문에 이 글을 작성하게 됐다. 다음의 글을 보고 두 번째 풀이로도 풀어보자는 생각을 했다.

프로그래머스

 

문자열이 들어있는 배열을 정렬하면, 접두사가 있는 경우 바로 직전/직후의 인덱스 위치에 놓인다는 것이다.

예를 들면 ['12', '13', '1212']을 정렬하면 ['12', '1212', '13']가 나오게 된다. '12'는 '1212'의 접두사로 바로 직전/직후의 위치에 놓여있다.

 

위 특성을 이용한 풀이 방식이다.

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

 

그렇게 위와 같이 풀이했다.

 

처음에 풀이할 때는 num[:i]에서 i가 num의 길이를 초과하면 어떡하지?라는 걱정을 해서 조건(len(phone_book[i]) < len(phone_book[i+1]))을 추가했었다. 하지만 파이썬에서 문자열을 자를 때, 크기가 넘으면 별도의 예외처리를 해주는 로직이 있기 때문에 문제가 되지 않는다.

 

따라서 위와 같은 최종 코드를 완성했다.