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

문제 설명
전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.
구조대 : 119
박준영 : 97 674 223
지영석 : 11 9552 4421
전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

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

풀이 00

1. 어떤 번호가 다른 번호의 접두어인 확인
2. 접두어일 경우, False이며, 접두어가 아닐 경우 True return

def solution(phone_book):    
    # 전화번호 목록을 해시맵으로 생성
    # 각 전화번호를 키(key)로, 값을 1로 설정
    hash_map = dict.fromkeys(phone_book, 1)
    # hash_map = {k:1 for k in phone_book}  # 위와 동일한 코드
    
    # 해시맵의 각 키(전화번호)에 대해 반복
    for key in hash_map.keys():
        prefix = ""  # 접두사를 저장할 변수 초기화
        # 현재 전화번호의 각 숫자(문자)를 순차적으로 확인
        for number in key:
            prefix += number  # 접두사에 숫자를 하나씩 추가
            # 접두사가 해시맵에 존재하고, 현재 키와 접두사가 다를 경우 (접두사가 자기 자신과 같은 경우 제외 위해)
            if prefix in hash_map and prefix != key:
                return False  # 접두사가 다른 번호의 시작 부분이므로 False 반환
    return True  # 접두사가 겹치는 경우가 없으면 True 반환

해시맵을 이용한 풀이로, 빠른 검색과 저장이 가능하다는 점을 이용하고자 했다.
해시맵을 생성한 후, 각 키를 순회하며 첫 번째 문자부터 순차적으로 접두사를 생성하여 검증하는 과정을 거친다. prefix in hash_map을 통해 접두사가 다른 전화번호의 시작 부분인지 확인하고 , prefix != key를 통해 접두사가 자기 자신과 같은 경우는 제외한다.

아래와 같이 과정을 상세하게 확인해 볼 수 있다.

phone_book = ["119", "97674223", "1195524421"]

def solution(phone_book):
    # 초기 상태의 답변 설정
    answer = True   
    # 전화번호 목록을 해시맵으로 생성
    hash_map = dict.fromkeys(phone_book, 1)  # 각 전화번호를 키(key)로 설정, 값은 1
    print("초기 해시맵:", hash_map)  # 생성된 해시맵 출력
    
    # 해시맵의 각 키(전화번호)에 대해 반복
    for key in hash_map.keys():
        print("\n현재 번호(key):", key)  # 현재 처리 중인 전화번호 출력
        prefix = ""  # 접두사를 저장할 변수 초기화
        # 현재 전화번호의 각 숫자(문자)를 순차적으로 확인
        for number in key:
            prefix += number  # 접두사에 숫자를 하나씩 추가
            print("생성된 접두사(prefix):", prefix)  # 현재 생성된 접두사 출력
            # 접두사가 해시맵에 존재하고, 현재 키와 접두사가 다를 경우
            if prefix in hash_map and prefix != key:
                print("접두사 존재:", prefix, "| 해시맵:", hash_map)  # 문제 발생 상황 출력
                answer = False  # 접두사가 겹치는 경우 답변을 False로 변경
                print("현재 answer 상태:", answer)  # 변경된 answer 확인
                return answer  # 접두사가 다른 번호의 시작 부분이므로 False 반환
    
        print("answer 상태:", answer)  # 최종 answer 상태 출력
    return answer  # 접두사가 겹치는 경우가 없으면 True 반환

print("\n결과:", solution(phone_book))

>>> 
초기 해시맵: {'119': 1, '97674223': 1, '1195524421': 1}

현재 번호(key): 119
생성된 접두사(prefix): 1
생성된 접두사(prefix): 11
생성된 접두사(prefix): 119
answer 상태: True

현재 번호(key): 97674223
생성된 접두사(prefix): 9
생성된 접두사(prefix): 97
생성된 접두사(prefix): 976
생성된 접두사(prefix): 9767
생성된 접두사(prefix): 97674
생성된 접두사(prefix): 976742
생성된 접두사(prefix): 9767422
생성된 접두사(prefix): 97674223
answer 상태: True

현재 번호(key): 1195524421
생성된 접두사(prefix): 1
생성된 접두사(prefix): 11
생성된 접두사(prefix): 119
접두사 존재: 119 | 해시맵: {'119': 1, '97674223': 1, '1195524421': 1}
현재 answer 상태: False

결과: False

풀이 01

• String1.startswitch(String2)
  • String1이 String2로 시작되는지 확인
  • 문자열이 특정문자로 시작하는지 여부를 알려줌 (true, false 반환)

해시를 사용한 풀이말고도 startswitch를 활용하여 String2가 String1의 접두어인지 찾아보는 방법이 존재한다.

def solution(phone_book):
    # 전화번호 목록을 정렬 (길이 순 또는 사전 순)
    # 정렬하면 접두사가 될 가능성이 있는 번호들이 인접하게 위치하게 됨
    phone_book.sort()

    # 인접한 두 번호만 비교
    for i in range(len(phone_book) - 1):
        # 현재 번호(phone_book[i])가 다음 번호(phone_book[i+1])의 접두사인지 확인
        if phone_book[i+1].startswith(phone_book[i]):
            return False  # 접두사를 발견한 경우 False 반환
        
    return True  # 접두사가 없는 경우 True 반환

전화번호 목록을 정렬하면, 접두사가 될 가능성이 있는 번호들이 서로 인접하게 배치된다. 따라서 이전에 확인한 번호와 그다음 번호만 비교하고, 정렬된 순서로 인해 이미 확인한 번호보다 뒤에 나오는 번호가 접두사일 가능성은 없으므로 양방향 비교가 필요하지 않고 단방향 비교만으로도 정답을 찾을 수 있다.

풀이 02

• zip(*iterables)
  • 여러 iterable(반복 가능한 객체)을 병렬로 순회하면서, 각 iterable의 동일한 인덱스에 있는 요소들을 튜플로 묶어서 반환하는 Python의 내장 함수
  • iterables: 반복 가능한 객체(예: 리스트, 튜플, 문자열 등)를 여러 개 받을 수 있음
  • 반환 값: 각 iterable의 요소들을 묶은 튜플들의 zip 객체 (반복 가능)
  • 동일한 인덱스의 요소를 묶음: zip 함수는 여러 iterable의 동일한 위치에 있는 요소를 튜플로 묶움
  • 최단 길이를 기준으로 동작: 입력된 iterable 중 가장 짧은 iterable의 길이를 기준으로 동작하며, 즉 더 긴 iterable의 나머지 요소는 무시
  • 반환값은 zip 객체로, 이를 사용하려면 반복문을 돌리거나 리스트로 변환해야 함 (* <zip object at 0x...> (zip 객체))
  • 입력 iterable 중 하나가 소진되면, 나머지 값은 무시

# 두 리스트를 묶기
a = [1, 2, 3]
b = ['a', 'b', 'c']

result = zip(a, b)
print(list(result))  # [(1, 'a'), (2, 'b'), (3, 'c')]

# 길이가 다른 iterable 처리
a = [1, 2, 3]
b = ['a', 'b']

result = zip(a, b)
print(list(result))  # [(1, 'a'), (2, 'b')]

# 여러 iterable 묶기
a = [1, 2, 3]
b = ['a', 'b', 'c']
c = [True, False, True]

result = zip(a, b, c)
print(list(result))  # [(1, 'a', True), (2, 'b', False), (3, 'c', True)]


# 인접한 요소를 비교
nums = [1, 2, 3, 4]

for x, y in zip(nums, nums[1:]):
    print(x, y)
# 출력:
# 1 2
# 2 3
# 3 4


# 두 리스트를 동시에 순회
names = ["Alice", "Bob", "Charlie"]
scores = [85, 92, 78]

for name, score in zip(names, scores):
    print(f"{name} scored {score}")
# 출력:
# Alice scored 85
# Bob scored 92
# Charlie scored 78

# 두 리스트를 합쳐서 딕셔너리 생성
keys = ['name', 'age', 'city']
values = ['Alice', 25, 'New York']

result = dict(zip(keys, values))
print(result)  # {'name': 'Alice', 'age': 25, 'city': 'New York'}

# 병렬 연산
a = [1, 2, 3]
b = [4, 5, 6]

result = [x + y for x, y in zip(a, b)]
print(result)  # [5, 7, 9]

# 데이터 정렬 후 인접한 값 비교
data = [10, 20, 15, 25, 30]
for x, y in zip(data, data[1:]):
    print(x, y)  # 출력: 인접한 값
    
# 리스트 변환 필수 
a = [1, 2, 3]
b = [4, 5, 6]

result = zip(a, b)
print(result)  # <zip object at 0x...> (zip 객체)
print(list(result))  # [(1, 4), (2, 5), (3, 6)] (리스트로 변환)

def solution(phone_book):
    # 전화번호 목록을 정렬 (길이 순 또는 사전 순)
    # 정렬하면 접두사가 될 가능성이 있는 번호들이 인접하게 위치하게 됨
    phone_book.sort()
    
    # zip을 사용해 인접한 두 번호를 묶어 반복
    for p1, p2 in zip(phone_book, phone_book[1:]):
        # p1이 p2의 접두사인지 확인
        if p2.startswith(p1):  # p2가 p1로 시작하면 접두사 관계
            return False  # 접두사를 발견한 경우 False 반환
    
    return True  # 접두사가 없는 경우 True 반환

전화번호 목록을 정렬한 후, zip 함수를 통해 본인과 다음 값을 묶음 처리해준다. 이후, for문을 통해 시작 단어를 검증한다.

---

참고

1. [프로그래머스] 전화번호 목록 _ Python 해시Lv.2
2. [프로그래머스] 전화번호 목록 문제 풀이(해시 Lv. 2) - 파이썬 Python