출처: 프로그래머스 코딩 테스트 연습
https://programmers.co.kr/learn/courses/30/lessons/42577
🔎 풀이 과정
해시 문제라, 처음에는 해시 테이블을 만들려고 했다. 첫 두세 글자를 키값으로 가지는 해시 테이블을 만들고자 했다. 하지만 이 경우 한자리 수를 처리하기 어렵기도 했고, 만약 첫 몇 글자가 같은 숫자로 몰려 있는 경우 해시 테이블의 분배 문제도 있었다. (실제로 대부분의 전화번호는 010으로 시작하므로, 만약 첫 세 글자를 key로 해시 테이블을 만들면 '010'을 key로 가지는 수만 넘칠 것이다.)
그래서 해시 테이블을 직접 만드는 대신, 정렬을 통해 문제를 해결했다. 이 풀이를 설명하려면 우선 파이썬의 문자열 정렬에 대해 이야기해야 한다. 파이썬의 경우, 문자열은 앞자리부터 문자 하나씩 대소를 비교한다. 두 문자열 중 짧은 문자열의 끝까지 긴 문자열과 같으면, 긴 문자열이 더 크다고 본다. (ex. 'abc' < 'abca' '파이' < '파이썬')
이 문제에서는 한 번호가 다른 번호의 접두사인지 판단해야 한다. 번호 A가 번호 B의 접두사라면, 번호 B는 번호 A에 숫자가 더 붙은 형태가 된다. 정렬하면 A가 오고, 다음에 B가 온다. 중요한 점은, 번호를 정렬했을 때 어떤 번호가 A와 B 사이에 온다면, 그 번호는 반드시 번호 A를 접두사로 가진다는 점이다. 문자열 정렬을 했을 때, 1234와 123456 사이에 어떤 숫자가 온다면, 그 숫자는 반드시 1234로 시작한다는 것이다.
따라서, 만약 번호 목록에 번호 A의 접두사가 존재한다면, 번호를 정렬했을 때 번호 A 다음에 오는 번호는 반드시 번호 A를 접두사로 가진다. 따라서 번호 목록 내에서 한 번호가 다른 번호를 접두사로 가지는지 알기 위해서는, 정렬한 뒤 i번째 번호가 i + 1번째 번호의 접두사인지만 검사하면 된다.
🔓 최종 풀이
def solution(phone_book):
phone_book.sort()
for i in range(len(phone_book) - 1):
if phone_book[i] == phone_book[i + 1][:len(phone_book[i])]:
return False
return True
바로 인접한 두 번호를 비교하기 위해, 인덱스를 사용하는 대신 zip 내장 함수를 사용할 수도 있다. 아래 풀이에서는 zip 내장 함수와 startswith 메서드를 사용했다.
def solution(phone_book):
phone_book.sort()
for before, current in zip(phone_book, phone_book[1:]):
if current.startswith(before):
return False
return True
