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

 

문제 설명

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

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

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

 

제한 사항

• phone_book의 길이는 1 이상 1,000,000 이하입니다.
  • 각 전화번호의 길이는 1 이상 20 이하입니다.
  • 같은 전화번호가 중복해서 들어있지 않습니다.

입출력 예제

phone_book	return
["119", "97674223", "1195524421"]	false
["123","456","789"]	true
["12","123","1235","567","88"]	false

입출력 예 설명

입출력 예 #1
앞에서 설명한 예와 같습니다.

입출력 예 #2
한 번호가 다른 번호의 접두사인 경우가 없으므로, 답은 true입니다.

입출력 예 #3
첫 번째 전화번호, “12”가 두 번째 전화번호 “123”의 접두사입니다. 따라서 답은 false입니다.

---

나의 답

def solution(phone_book):
    p = {}
    for num in phone_book:
        p[num] = True
    for num in phone_book:
        piece = ''
        for i in num[:-1]:
            piece += i
            if piece in p:
                answer = False
                return answer
    
    answer = True
    return answer

• 처음에 길이가 작은 번호가 다른 긴 번호의 시작이라면, false를 반환하면 되겠지라는 생각으로 접근했다가 결국 혼자 ㅎ미으로 풀지 못한 문제입니다. 
  • 즉 처음에는 "짧은 번호가 긴 번호의 접두사인지"만 체크하면 된다고 생각했습니다.
  • "12"가 "123"의 접두사인 경우는 쉽게 떠올릴 수 있지만, 반대로 "123"처럼 긴 번호에서 접두사를 하나씩 잘라가면서 존재하는 번호인지 확인해야 한다는 발상이 부족했습니다.
• 이 문제는 “내 번호가 접두사이냐”가 아니라,
  “내 번호를 구성하는 접두사들 중에, 실제 존재하는 번호가 있느냐”라는 생각으로 접근해야 풀리는 문제입니다.

 

• 왜 해시(dict)를 쓰는가?
  • 리스트에서 어떤 값이 존재하는지를 검사하려면, 아래와 같습니다.
  • 아래의 경우,  리스트의 앞에서부터 하나씩 비교해야 해서, 최악의 경우 O(n) 시간복잡도가 걸립니다.

  • "119" in phone_book  # 리스트일 경우 → O(n)

  • 이건 리스트의 앞에서부터 하나씩 비교해야 해서, 최악의 경우 O(n) 시간복잡도가 걸립니다.
  • 반면, 딕셔너리(dict)는 내부적으로 해시 테이블을 사용하여 값을 저장하므로
  • → 해시값을 기반으로 바로 위치를 찾아가 탐색하므로 매우 빠릅니다.
    전화번호 개수가 수십만 개일 수 있으므로, 이런 최적화가 필수입니다.

"119" in p  # 딕셔너리일 경우 → O(1) (평균)

 

결론

 

• 문제를 반대로 생각하는 훈련이 필요하다 → “내가 다른 번호의 접두사인가?”뿐 아니라, “내 번호를 자르면 누군가의 번호가 나올 수도 있다”는 점
• 문자열 검색/탐색이 많으면 해시를 써라 → 리스트보다 압도적으로 빠른 성능
• in dict 또는 in set 연산은 내부적으로 해시 기반이라 O(1)이다