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

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

프로그래머스

 

 

✅ 정답풀이 (배열)

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

 

이전에, JS로 한번 풀어본 문제라서 금방 해결할 수 있었다.

⚡️ 이 문제의 포인트는 접두사가 포함되는지 여부를 확인하는것이기 때문에 sort로 정렬한 상태에서는 바로 다음요소만 확인하면 된다는 점이다.

 

정렬된 상태이기 때문에, 그것도 일부가 아닌 한 단어 전체가 접두어가 되어야해서, 자신을 기준으로 다음 단어가 접두사의 조건을 충족하지 못하면 이후의 단어들은 확인해볼 필요가 없다.

 

 

 

 

 

✅ 정답풀이 (해시)

for문을 순회하면서 다음 요소를 확인하는 식으로 풀이하였는데, 문제의 카테고리가 해시길래

한번 해시로 다시 문제를 풀어보았다.

 

def solution(phone_book):
    phone_map = {}

    for number in phone_book:
        phone_map[number]=True

    for number in phone_book:
        for i in range(1,len(number)):
            prefix=number[:i] # 가능한 모든 후보 접두어 생성
            if prefix in phone_map:
                return False

    return True

 

음 되게 정직한 방법으로 푸는 방법인것 같다.

 

일단, 모든 단어를 map을 생성해서 넣어주고, 모든 단어들에 대해 가능한 접두어를 생성해준다.

그리고 그 접두어가 생성해둔 map에 존재하는지 여부를 확인한다.