프로그래머스> 해시 > 전화번호 목록

 

<문제링크: https://programmers.co.kr/learn/courses/30/lessons/42577>

코딩테스트 연습 - 전화번호 목록

 

문제설명: phone_book 리스트에 주어지는 번호들 중 한 개의 번호가 다른 번호의 앞자리와 일치하는지 판별하는 문제이다. 즉 이 조건을 한 번이라도 만족한다면 false를 반환하고, 그렇지 않으면 주어지는 defult 값 true를 반환한다.

 

 

[1차 시도]

def solution(phone_book):
    answer = True
    i = 0
    while i != len(phone_book)-1:
        for p in phone_book:
            if phone_book[i] != p and p[0:len(phone_book[i])] == phone_book[i]:
                answer = False
                break
        i+=1
    return answer

 

풀이: while반복문으로 앞에서부터 번호들을 하나씩 검사하면서 전체 번호들 중 현재 비교하고자 하는 번호와 일치하지 않고, 동시에 0부터 현재 번호 길이까지의 인덱스로 비교하여 앞자리 번호 일치여부를 검사한다. 맞다면 answer를 False로 바꿔주고 바로 break를 걸어 반복문을 종료한다.

 

채첨 결과: 정확성 테스트에서는 통과하지만, 효율성 테스트에서는 시간초과로 나온다.

 

해결방법: 이렇게 하면 첫 번째 번호부터 차례로 돌기 때문에 시간이 많이 걸리고, 어차피 한 개의 번호가 다른 번호의 앞자리와 일치하는지만 판별하면 되므로 가장 짧은 숫자를 먼저 찾아서 기준으로 삼고 탐색해도 된다.

 

 

[2차 시도]

def solution(phone_book):
    answer = True
    target = min(phone_book)
    for p in phone_book:
        if p != target and p[0:len(target)]== target:
            answer = False
            break
    return answer

 

풀이: 번호들 중 가장 짧은 번호를 찾아 target으로 선정하고, 전체 번호들을 순회하며 target 번호와 일치하지 않으면서 동시에 0부터 target 번호의 길이까지 인덱스로 비교하여 앞자리 번호의 일치여부를 검사한다. 혹은 그냥 <-- if p != target and target in p: --> 라고 해도 통과하지만, 문제에서 '다른 번호의 접두어인 경우'라고 했으므로 인덱싱을 사용하는게 맞다고 본다. 따라서 일치 한다면 answer를 False로 바꿔주고 바로 break를 걸어 반복문을 종료한다.

 

채첨결과: 정확성, 효율성 모두 정상적으로 잘 통과한다.