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

 

출처 : 프로그래머스, https://programmers.co.kr/learn/courses/30/lessons/42577

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

LV2로 들어오니까 별 생각 없이 풀면 되던 LV1에 비해 갑자기 난이도가 확 상승한 느낌이라

LV2를 본격적으로 풀어보기 전에 코딩테스트 고득점 Kit에서 분야별로 정해서 LV2까지 문제를 모두 풀어보고

LV2 문제를 풀어보려고 계획을 잡고, 해싱부터 시작하였다.

 

접두사랑 접두어라는 용어가 나오는데

 

• 접두사 : 어떤 단어의 앞에 붙어 새로운 단어가 되게 하는 말
• 접두어 : 접두사가 앞에 붙어 만들어진 단어

라는 뜻이다. 숫자에서 무슨 접두사야 하고 뭔소린가 싶어서 보다가 이해를 좀 늦게 했는데

여기서는 숫자이므로 새로운 단어까진 보지말고 내 번호가 앞에 붙은 다른 전화번호가 있느냐

라는 의미로 쓰인 것이므로 그냥 앞에 붙냐 아니냐만 보면 되겠다.

 

 

1. 첫 번째 풀이 : 효율성 테스트 실패

 

def solution(phone_book):
    phone_book = sorted(phone_book, key=lambda x : (len(x), sorted(x)))
    
    for index in range(len(phone_book)):
        for index2 in range(index + 1, len(phone_book)):
            if phone_book[index] == phone_book[index2][:len(phone_book[index])]:
                return False

    return True

(길이 다음 사전식 정렬을 위해선 len(x), sorted(x)가 아니라 len(x), x가 맞는 표현)

 

앞에 붙고 아니고를 판단하려면 결국 문자열의 길이가 나보다 같거나 길면 된다는 점에서 착안한 풀이이다.

정렬 조건에 len와 sorted 함수를 1차, 2차 조건으로 사용하여 len으로 먼저 정렬 후

sorted로 사전순으로 정렬되게 만들면 내 앞에 정렬된 녀석들은 무조건 나를 포함하지 않으므로

뒤에 정렬된 녀석들만 가져와서 내 길이만큼 비교해서 포함 여부를 판단하는 풀이인데,

예상은 했지만  for문을 2번 사용해서 그런지 효율성 테스트 3번, 4번을 통과하지 못했다.

 

 

2. 두 번째 풀이 : 질문하기 참고 성공

 

def solution(phone_book):
    phone_book = sorted(phone_book, key=lambda x : (x, len(x)))

    for index in range(len(phone_book) - 1):
        if phone_book[index] == phone_book[index + 1][:len(phone_book[index])]:
            return False
    
    return True

 

첫 번째 풀이에서 길이로 먼저 정렬하고 값으로 정렬을 했다면,

이번엔 반대로 생각해 값을 먼저 정렬하고, 그 다음 길이로 정렬하는 것이다.

예를 들어 123, 124, 1243, 1234가 있다면 숫자가 아닌 문자열이기 때문에 값으로 정렬하면 사전식으로 정렬된다.

그 후 길이를 기준으로 정렬하면 123, 1234, 124, 1243 순으로 정렬되게 된다.

 

이렇게 정렬하는 풀이가 이점이 있는 이유는 바로 탐색 범위를 획기적으로 줄일 수 있다는 점인데

사전식으로 정렬된 것이 먼저이기 때문에 123456789 순서대로 정렬이 먼저 되고 안에서 길이 순으로 정렬되어

나와 바로 다음 값만 비교하여 내 다음 값에 내가 포함되어있는지만 따지면 되기 때문이다.

(위의 123, 1234, 124, 1243 예제처럼 123과 1234가 124보다 앞에 위치한다)

이는 곧 엄청난 시간 단축을 보여준다.

 

3. 세 번째 풀이

 

def solution(phone_book):
    phone_book = sorted(phone_book)

    for index in range(len(phone_book) - 1):
        if phone_book[index] == phone_book[index + 1][:len(phone_book[index])]:
            return False

    return True

 

이 풀이는 같이 코딩 테스트 문제를 풀면서 풀이를 공유하는 분과 얘기하며 나온 코드인데

뭐가 바뀌었냐면 길이 정렬 할 필요가 없다.....충격과 공포.........난 대체 무엇 때문에.......................

 

사전식 정렬하면서 앞이 같으면서 뒤에 무언가 있는 문자열은 사전 순서상으로도 뒤로 밀리기 때문에

길이 정렬 없이도 길이 정렬이 된 것처럼 동작하는 것이다.

---

시간 복잡도

 

시간 복잡도를 한 번 계산해보면 sorted 함수의 시간 복잡도는 O(NlogN)이므로

첫 번째 풀이는 밖의 for문에서 전체 한번 돌 때 N, 루프 한번 당 N씩 돌기 때문에 O(N^2)

두 번째 풀이는 for문 상에서는 전체 한 번만 돌기 때문에 O(N)이지만 sorted함수로 인해 O(NlogN)이다.

세 번째 풀이 역시 두 번째와 동일하게 O(NlogN)이다.

느낌상 효율성 테스트에서 N^2이 나오면 그냥 틀린거더라...

 

 

다른 사람의 풀이를 보면서 알게 된 점

 

1. startswith(), endswith()

 

if phone_book[index] == phone_book[index + 1][:len(phone_book[index])]:

 

위와 같이 어떤 문자열이 다른 문자열의 시작부에 있는지 체크하는 코드가 있는데

이를 해주는 함수가 따로 존재한다. 바로 startswith 함수이다.

 

if phone_book[index+1].startswith(phone_book[index]):

 

과 같이 사용가능하다. 반대로 끝부분에 있는지 검사하는 함수는 endswith()

 

2. Hashing을 이용한 풀이

 

사실 원래 이 문제의 카테고리가 해싱인데 난 딱히 해싱으로 풀지 않았다 ㅎ...

해싱으로 푼 풀이가 있어서 가져오고 싶은데 복붙은 또 안 될것 같고 해서 모방해서 적어봤다.

 

def solution(phone_book):
    phone_dict = dict.fromkeys(phone_book, 0)
    
    for phone_number in phone_book:
        part_num = ""
        
        for num in phone_number:
            part_num += num
            
            if part_num in phone_dict and part_num != phone_number:
                return False
            
    return True

 

파이썬에서 해싱으로 만들어진 자료형 중 대표적인 하나가 바로 사전 자료형이다.

위 풀이는 이 사전 자료형을 사용한 풀이인데 로직은 다음과 같다.

 

• phone_book이라는 list를 번호를 key로하는 사전 자료형인 phone_dict으로 만든다. (value는 0)
• phone_book 안에 있는 번호를 for문을 통해 하나씩 가져온다.(phone_number)
• phone_number에서 한 글자씩 가져와서 part_num에 추가한다
• part_num이 phone_dict에 있으면서 전체 전화번호가 아닌지 확인한다. 조건 충족 시 return False
• for문을 모두 통과하면 return True

즉, phone_number의 일부분을 가져와 만든 사전 자료형에 in 연산자로 있는지 여부를 체크하는 방식이다.

시간복잡도는, 사전 자료형을 만드는 fromkeys가 O(N),

밖의 for문에서 N번 루프를 도는데 안쪽 루프에서는 전화번호 길이에 제한이 있으므로(1≤길이≤20) 전체 for문은 O(N)

문제는 in 연산자의 시간 복잡도인데 검색해본 결과 list 자료형에서는 O(N)이지만

집합, 사전 자료형의 경우 hash function에 따라 O(1) ~ O(N)까지 달라진다고 한다.

이에 따라 전체 시간복잡도는 O(N) ~ O(N^2)이다.

 

 

고찰

 

처음에 접근할 때는 저걸 어떻게 일일이 다 비교하지 라는 생각으로 막막했는데

sorted를 통해 탐색 범위를 줄이면서 풀이의 방향이 보였다. 그 방향을 반대로 생각한게 안타깝지만....

사실 정렬을 통해 탐색 범위를 줄이는건 다른 풀이에서도 많이 쓰이기 때문에

일단 모든 데이터를 탐색해야하고 범위가 많다 싶으면

정렬로 범위를 줄여 이득을 볼 수 있는지 먼저 생각해 봐야할 듯 하다.

그리고 zip 함수를 공부해야겠다....다른 사람 풀이 보면 맨날 있어...