프로그래머스 Lv2 문제입니다. 실전에 대비하기 위해 60분 시간제한을 두고 풀었습니다.

문제

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

⌛ 시간 초과 (22/24 성공, 2개 케이스 시간 초과,제한 시간 이후 해결)

import copy

def solution(phone_book):
    
    for num in phone_book:
        tmp = phone_book.copy()
        tmp.remove(num)
        
        dic = {}
        dic[num] = hash(num)
        
        for x in tmp:

            if len(num)!=len(x):
                if hash(x[:len(num)]) in dic.values():
                    return False
            
    return True

입력된 전화 번호 목록(phone_book)에서 어떠한 전화 번호 1개가 다른 전화 번호의 접두어 일 때 False, 아니라면 True를 반환하는 문제입니다.

2중 loop문을 통해 구현하고자 하였습니다.

첫번째 loop문에서 현재 전화 번호(num)를 key-value 형태로 저장하고 이를 제외한 전화 번호 목록(tmp) 중 현재 전화 번호를 접두어로 하는 번호가 있는지 조사하였습니다.

위와 같이 구현하여 모두 정답을 구할 수 있지만 2개 효율성 테스트에서 만족하지 못하였고 다른 풀이를 참고하였습니다.

[다른 사람의 풀이1]

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

정렬을 활용한 풀이입니다.

입력되는 전화 번호 목록을 정렬 한다면, 현재 인덱스와 다음 인덱스의 요소만 비교하면 되기 때문에 1중 loop문으로 줄일 수 있는 알고리즘이였습니다.

[다른 사람의 풀이2]

def solution(phone_book):
        
    dic = {}
    for num in phone_book:
        dic[num] = 1
    # print(dic)
    
    for num in phone_book:
        tmp = ""
        for x in num:
            tmp += x
            if tmp in dic and tmp !=num:
                return False
            
    return True

해시맵을 활용한 풀이입니다. 가장 정석적인 풀이라고 볼 수 있습니다.

입력된 전화 번호 목록(phone_book)을 Key(Value==1)로 하여 HashMap(dic)에 저장한 뒤, 현재 전화 번호(num)를 기준으로 다른 전화번호들(for x in tmp)의 전화번호를 쪼개어 덧셈 연산해보며 HashMap에 존재하는지만 판별하면 되는 문제였습니다.

이때,

if tmp in dic 

과 같은 구문으로 해시맵을 활용하여 탐색하는 것이 시간을 줄이는 포인트였습니다.

감사합니다.