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

1. 문제 설명

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

• 구조대 : 119
• 박준영 : 97 674 223
• 지영석 : 11 9552 4421

전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

2. 제한사항

• phone_book의 길이는 1 이상 1,000,000 이하입니다.
• 각 전화번호의 길이는 1 이상 20 이하입니다.

3. 풀이 과정

def solution(phone_book):
    answer = True
    
    for i in phone_book:
        for j in phone_book:
            if i != j and i in j:
                answer = False
                
    return answer

문제를 보자마자 떠오른 해결법이다. 이중 for문을 쓰고 있어서 사실상 효율성에서는 좋은 점수를 받을 거 같지 않고, 정확도라도 한 번 검사해보자는 생각으로 작성했던 코드이다. 하지만 의아하게도 정확도마저 만점이 나오지 않았다. 이를 곰곰이 생각해보니 in 연산을 사용하는 것은 적절하지 않았다. 예를 들어 ["123", "3123", "456"] 인 테스트 케이스가 있다면 123이 3123의 접두어가 아닌데도 불구하고 False를 반환하는 문제가 있었다.

def solution(phone_book):
    answer = True
    
    for i in phone_book:
        for j in phone_book:
            if i != j and i.startswith(j):
                answer = False
                
    return answer

startswith로 교체하고 실행한 결과 정확도에서는 만점을 받을 수 있었다.

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

더 궁리해본 결과, 정렬을 통해서 생각보다 쉽게 해결할 수 있었다. 예를 들어 [567, 12, 123, 345] 라는 테스트 케이스가 있다면 정렬을 하면 [12, 123, 345, 567]이 된다. 자연스럽게 뒤에 있는 전화번호가 앞에 있는 전화번호를 포함하고 있는지만 체크하면 되기 때문에 for문도 1개로 줄어들고 더욱 효율적으로 풀 수 있었다.

4. 문제 링크

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