프로그래머스(Programmers) 전화번호 목록 - python 풀이

JISU LIM·2023년 1월 11일

Algorithm Study Records

목록 보기

24/79

❓프로그래머스 : 전화번호 목록

〽️ 문제 요약

전화번호부에 있는 특정 수가 다른 수의 prefix에 해당하는 경우가 존재하는지 판단하는 문제

🤨 접근법1 : 정렬을 통한 prefix 여부 확인

처음에는 브루트 포스로 모든 두 전화번호를 비교하는 경우에 대해서 다른 수의 prefix에 해당하는 수가 있는지를 찾았다. 예상했던 대로 시간 초과가 발생했다.

다른 방법이 도저히 떠오르지 않아 레퍼런스를 참고했다.

해답은 간단했지만 놓치고 생각하기 쉬운 것이었다. 바로 문자열끼리의 정렬은 수 끼리의 정렬과 많은 부분 차이가 있다는 점을 활용하는 것이다. 수 끼리의 정렬 과정에서는 무조건 수의 크기를 기준으로 정렬을 수행하지만, 문자열끼리의 정렬 과정에서는 맨 앞 글자부터 아스키 코드상 기준으로 비교하고, 문자열의 길이가 다른 경우 같은 길이까지만 봤을 때 아스키 코드 기준, 같다면 길이가 작은 순으로 정렬된다. 예를 들어 [”12”, “1235”, “123”, “88”, “567”]을 정렬하면 [”12”, “123”, “1235”, “567”, “88”]이 된다.

따라서 어떤 수(문자열)가 다른 수(문자열)의 prefix인지 확인하기 위해서는 i번 째 문자열이 i+1번째 문자열의 맨 앞에 해당하는지만 확인하면 된다. 정렬을 통해 경우의 수를 줄일 수 있기 떄문에 시간 초과를 해결할 수 있다.

🔡 코드 1

def solution(phone_book):
    phone_book.sort()
    n = len(phone_book)
    for i in range(n-1):
        if phone_book[i] == phone_book[i+1][:len(phone_book[i])]:
            return False
#				if phone_book[i+1].startwith(phone_book[i]):
#						return False
    return True

주석 처리된 부분은 동일 과정을 문자열 메소드 중 하나인 startwith 메소드를 이용한 방법이다.

🤨 접근법 2 : 해시를 통한 풀이

본 문제의 유형인 해시를 통한 풀이이다. phone_book에 있는 각 문자열을 순회하여 모두 해시 테이블에 저장해 활용한다.

다시 phone_book에 있는 각 문자열을 순회하여 각 문자열의 원소를 하나씩 더해가며 다른 해시 테이블 내 문자열과 같은지 비교한다. 즉, 다른 문자열이 현재 문자열의 prefix인지 찾는 것이다. 일반적인 브루트 포스 방식과 다를 것 없어 보여도, 해시 테이블을 활용했기 때문에 element의 존재를 검사하는 연산에 대한 비용이 리스트 등의 선형 자료구조에 비해 적어서 빠르다.

🔡 코드 2

def solution2(phone_book):
    hash_map = {}
    for num in phone_book:
        hash_map[num] = 1
    for num in phone_book:
        tmp = ""
        for n in num:
            tmp += n
            if tmp in hash_map and tmp != num:
                return False
    return True