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

문제

---

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

프로그래머스

입출력

---

 

해설

---

 

하나의 전화번호가 다른 전화번호의 접두어로 존재하지 않으면 True, 존재하면 False를 리턴하는 문제이다.

 

해당 문제를 풀기 위해 다음과 같은 생각을 했다.

 

1. 정렬을 하여서 접두어가 인접한 idx끼리는 접두어가 겹치게끔 했다.

2. 정렬의 핵심은 접두어가 겹치는 것과 길이가 작은 순으로 하였다.

3. 현재 i라는 인덱스의 문자를 보고 있을 때 i + 1 <= x < len(phone_book)의 idx에서 현재 문자가 있지 않는다면

    더이상 뒤의 idx를 볼필요가 없게 하였다.

 

위와 같은 생각으로 처음으로 정렬을 하였다. O(nlogn)

그럼 다음과 같이 정렬이 된다.

 

ex)

전 : ["123", "362711", "123561", "12821", "12381", "12992"]

후 : ["123", "123561", "12381", "12821", "12992", "362711"]

 

이렇게 됐을 때 0번 인덱스일 때 123이 다음 인덱스 문자에 포함이 되는지 확인했다. O(N)

그 다음 접두어로 존재하는지 처음 문자부터 하나씩 확인했다. O(N)

 

정답코드

---

def solution(phone_book):
    answer = True
    phone_book.sort(key = lambda x: (x, len(x)))
    
    #print(phone_book)
    #해시로 만든다?
    
    #접두어로 있다..
    #118
    #1194
    #11946
    #119478 이런 케이스가 있을 수도 있다.
    #11821787823 << 이런케이스를 빠르게 구할 수있으려면
    

    for idx, phone_number in enumerate(phone_book):
        for next_idx in range(idx + 1, len(phone_book)):
            if phone_number not in phone_book[next_idx]:break
            #첫 글자가 다르면 더이상 볼 필요가 없음
            A_idx = B_idx = 0
            while A_idx < len(phone_number) and B_idx < len(phone_book[next_idx]) and \
                phone_number[A_idx] == phone_book[next_idx][B_idx]:
                A_idx += 1
                B_idx += 1
            
            if A_idx == len(phone_number):
                answer = False
        
    return answer

 

깃허브 : https://buly.kr/5fDFGuy

유튜브 : https://youtu.be/ibIZRx0RpvU