[프로그래머스 해시]전화번호 목록 - Python3

문제

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

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

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

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

코딩테스트 연습 - 전화번호 목록 | 프로그래머스

 

입력

• 전화번호를 나타내는 문자열의 배열

출력

• 접두어가 있는지 없는지 여부. 있다면 False를, 있다면 True를 리턴한다.

 

알고리즘

# 해쉬 사용 안함.
def solution(phone_book):
    answer = True
    # phone_book을 원소의 길이가 짧은 순서대로 정렬한다.
    phone_book.sort(key=len)

    # 2중 while문을 돌린다.
    i = 0
    while i < len(phone_book):
        j = i + 1

        # i번째 원소와, i+1, i+2, ... , N번째 원소를 비교한다.
        # i번째 원소의 길이를 length에 저장해두고, j번째 원소의 0~length-1 까지의 값을 비교한다
        # 즉, i번째 원소가 "123"인데, j번째 요소가 "12345"라면,
        # i번째 원소인 "123"과 j번째 원소의 0 ~ 2번째까지의 값인 "123을 비교한다. 같다면 False를 리턴한다.
        while j < len(phone_book):
            length = len(phone_book[i])
            if phone_book[i] == phone_book[j][0:length]:
                return False
            else:
                j += 1
        i += 1

    return answer


phone_book = ["12", "123", "1235", "567", "88"]
print(solution(phone_book))

 

설명

1. 배열의 원소들을, 각 원소의 길이를 기준으로 정렬한다. 그 이유는, 한 원소가 다른 원소의 접두어이기 위해선 한 원소가 다른 원소보다 길이가 짧아야하기 때문이다. 정렬을 하지 않아도 되는 더 좋은 방법이 있을 것이다. 
2. 2중 while문을 돌려서, i번째 원소와 그 이후에 나오는 원소들을 비교한다. 왜 2중 for문이 아닌 while문을 썼냐면 필자가 파이썬 for문을 아직 완벽하게 사용하지 못하기 때문이다. 뭐 for문이나 while문이나 서로 대체할 수가 있으니 일단 이 문제에서는 while문으로 사용했다. 
3. 2번째 while문 안에서 값을 비교를 하게 된다. 이 때 in을 사용하게 되면, 접두관계가 아니라 포함관계 여부를 비교하게 되므로 사용하지 않았다. 주석에도 달아놨듯이, i번째 원소가 "12345"이고 j번째 원소가 "12345678"이라면 i번째 원소인 "12345"와 j번째 원소의 [0:5], 즉 "12345"까지를 비교한다. 
4. 두 값이 같다면 False를 리턴하고, 그렇지 않다면 j를 1 증가시켜서 반복을 진행한다.

결과

원하는 결과를 출력한다.

 

후기

사실 이 문제는 "해시"를 사용해서 푸는 문제로 올라와있었다. 근데 도무지 어떻게 해시를 사용해야 풀지를 모르겠어서, 일단 가장 단순한 방법으로 풀어보려고 했다. 정확성 테스트는 통과하고 효율성 테스트는 떨어질 줄 알았는데, 위 방법으로 효율성 테스트 또한 통과했다. 그러나 실제 코딩테스트에서는 저 코드로는 통과하지 못할 가능성이 크다. 왜냐하면 코딩테스트에서는 더 효율적인 방법을 요구하기 때문에, 입력 데이터가 지금보다 훨씬 클 것이기 때문이다. 지금의 알고리즘은 O(N^2)의 시간복잡도를 갖는데, 이러면 무적권 떨어진다. 그러니까 혹시 해시를 이용해서 풀 수 있는 방법을 아는 자는 속히 댓글을 달아주길 바란다. 

또한, 파이썬 for문을 내가 아직 잘 사용을 못하는 것 같다. 뭐 크게 상관 있겠냐마는 아무래도 전에 자바나 씨를 공부할때는 For문을 많이 썼어서 그런지 좀 어색하다. 열심히 공부해야겠다. 그리고 파이썬 내장 메소드 중에 startWith()이라는 메소가 있어서, 굳이 저렇게 비교를 안해도 된다고 한다. 여윾시 파이썬 짱짱~~~~