프로그래머스 Lv.2 | Python | 전화번호 목록

1. 문제 정보

프로그래머스

• 난이도: Lv.2

---

2. 문제 설명

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

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

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

제한 조건

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

---

3. 접근 기준

처음에는 모든 번호를 서로 비교해야 할 것처럼 보인다. 하지만 실제로는 모든 조합을 비교할 필요가 없다.

핵심은 문자열을 정렬하면:

접두어 관계인 문자열끼리 서로 가까워진다

는 점이다.

예를 들어:

["119", "1195524421", "97674223"]

처럼 정렬되면,
접두어 여부는 인접한 문자열끼리만 확인해도 된다.

• 문자열 정렬
• 바로 옆 문자열끼리 접두어 확인

이 흐름으로 접근하면 된다.

---

4. 사용한 패턴 / 알고리즘

정렬 (Sorting)

• 문자열 사전순 정렬

문자열 함수

• startswith() 활용

---

5. 핵심 아이디어

핵심은 정렬하면 접두어 관계인 문자열이 서로 붙는다는 점이다.

예:

["12", "123", "567", "88"]

정렬 후:

["12", "123", "567", "88"]

여기서 "123"은 "12"로 시작한다.

즉:

"123".startswith("12")

만 확인하면 된다. 전체를 전부 비교할 필요 없이, 정렬 후 바로 옆 문자열만 비교하면 접두어 여부를 찾을 수 있다.

---

6. 풀이 코드

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

이 코드의 핵심은:

startswith()

함수와 정렬 아이디어다.

6-1) 왜 정렬하는가?

예를 들어 다음 번호들이 있다고 하자.

["119", "97674223", "1195524421"]

정렬하면:

["119", "1195524421", "97674223"]

이렇게 된다.

즉, 접두어 관계인 문자열들이 서로 붙게 된다

그래서 전체를 다 비교하지 않아도 현재 문자열 vs 바로 이전 문자열 비교하면 된다.

6-2) startswith란?

문자열.startswith(문자열)

형태로 사용한다.

예:

"1195524421".startswith("119")

결과:

True

즉, 현재 문자열이 특정 문자열로 시작하는가? 를 확인하는 함수다.

6-3) 왜 인접한 값만 비교하는가?

정렬 상태에서는 접두어 가능성이 있는 문자열이 반드시 근처에 위치한다.

["12", "123", "1235", "88"]

여기서 "12"와 관련 있는 문자열은 바로 뒤에 몰려 있다.

그래서:

phone_book[i]
phone_book[i - 1]

만 비교해도 충분하다.

---

7. 핵심 로직 요약

이 문제의 핵심은 정렬 후 인접한 문자열만 비교해서 접두어 여부를 확인하는 것이다.

• 전화번호를 문자열 기준으로 정렬한다.
• 인접한 번호끼리 비교한다.
• 현재 번호가 이전 번호로 시작하면 False 반환
• 끝까지 없으면 True 반환

결국, “정렬 + startswith 활용” 이 구조가 핵심이다.

---

8. 정리

처음 보면 모든 번호를 전부 비교해야 할 것처럼 느껴진다.
근데 실제로는 정렬 하나로 문제 구조가 단순해진다.

특히 핵심은 이거였다.

정렬하면 접두어 후보가 서로 붙는다

이 아이디어를 떠올리면 복잡한 탐색 없이 바로 해결할 수 있다.

또 startswith() 함수도 문자열 문제에서 굉장히 자주 나온다.

결국 이 문제는 문자열 비교 문제라기보다, 정렬을 이용해 비교 범위를 줄이는 문제라는 느낌이 강했다.

---

번외) 해시(Set)를 활용한 풀이

정렬 말고도 set을 이용해서 풀 수 있다.

def solution(phone_book):

    # 전화번호 존재 여부를 빠르게 확인하기 위해 set 사용
    # set의 in 연산은 평균 O(1)
    phone_set = set(phone_book)

    # 모든 전화번호 순회
    for phone in phone_book:

        # 자기 자신 전체 번호는 제외해야 하므로
        # len(phone) 전까지만 확인
        for i in range(1, len(phone)):

            # 앞부분(prefix) 생성
            prefix = phone[:i]

            # 접두어가 실제 전화번호 목록에 존재하면
            if prefix in phone_set:
                return False

    return True

이 풀이의 핵심

예를 들어:

"1195524421"

라는 번호가 있으면:

1
11
119
1195 ...

처럼 앞부분을 계속 잘라본다.

그리고:

if prefix in phone_set

를 통해 해당 접두어가 실제 전화번호 목록에 존재하는지 확인한다.

즉:

• 접두어 직접 생성
• set으로 빠르게 존재 여부 확인

이 흐름이다.

정렬 풀이와의 차이

정렬 풀이:

접두어 후보만 비교

• 정렬 후 인접한 값만 확인
• 코드가 짧고 직관적
• 실전에서 더 자주 사용

set 풀이:

접두어를 직접 생성해서 확인

• 해시 활용 연습 가능
• 접두어 개념이 더 직접적으로 보임
• 문자열 슬라이싱 반복 발생