프로그래머스) 전화번호 목록 - python 해시

프로그래머스

💡 나의 접근 방법

---

1. "문자열" + x 를 이중 반복문을 통해서 확인한다? -> 최악의 경우 O(n^1) 시간발생

2. 해시로 모든 값을 저장하고 replace() 이용?

3. 정렬을해 길이가 짧은것부터 탐색한다? 

 

 

✨ 정답

---

정렬을 이용하는 방법

정렬 sort를 이용하지만, 나는 각 인덱스의 len() 순서대로 정렬을 생각했다. 문제에서는 숫자로 된 문자열이였고, 이는 정렬에 활용할 수 있다.

1️⃣ 접근 방법 1

문자열을 정렬시 오름차순으로 정렬하게 되어있다.

숫자 문자열의 경우 앞에서부터 차례대로 오름차순으로 정렬하기 때문에

[“10”, “1”, “5”] 의 경우 [’1’, ‘10’, ‘5’]로 출력되게 됨을 이용한다.

 

정렬을 하게 되면 리스트 내에서 1과 2,3,4.. 로 이중 비교할것을 앞에서 부터 1,2/ 2,3/ 3,4/.. 만 비교하여 접두사인지 확인할 수 있다.

 

2️⃣ 접근 방법 2

정렬된 리스트를 앞에서 부터 2개씩 비교하면 된다.

여기서 zip() 함수를 이용할 수 있다. list, list[1:]를 zip() 함수로 묶으면 1,2/ 2,3/ 3,4/… 로 묶을 수 있다.

 

3️⃣ 접근 방법 3

a.startswith(b) 는 a가 b로 시작되는지 확인하는 함수이다.

p2.startswith(p1) 뒤에 값을 앞의 값으로 시작하는 지 확인한다.

 

def solution(phone_book):
    answer = True
    phone_book = sorted(phone_book)

    for p1,p2 in zip(phone_book,phone_book[1:]):
        if p2.startswith(p1):
            answer = False
            return answer
    return answer

 

해시를 이용하는 방법

1번째 방법으로 문제를 풀 수 있다. 해시 딕셔너리에 모든 값을 넣는다. 

그리고 전화번호를 하나씩 저장해나가면서 딕셔너리에 값을 값이 있는지 확인한다.

def solution(phone_book):
    hash_map = {}
    for phone_number in phone_book:
        hash_map[phone_number] = 1

    for phone_number in phone_book:
        jubdoo = ""
        for number in phone_number:
            jubdoo += number  
            if jubdoo in hash_map and jubdoo != phone_number:
                return False
    return True

 

이 문제에서는 정렬을 이용해 문제 푸는데 시간적으로 더 효율적인것 같다.