🏀 문제

https://programmers.co.kr/learn/courses/30/lessons/42577

문제는 따로 설명하지 않고, 링크를 첨부.

💡 접근 방식

두 가지를 먼저 고민함.

• 비교를 어떻게 할 것인가?

  전화번화부 자체를 prefix로 두고 비교를 하자. 그 경우, phone_book을 기반으로 이 중 for문을 돌리면 모든 케이스에 대해서 비교가 가능하다고 생각.

• prefix 의 케이스가 이중 for문으로 한다면 prefix라는게 보장이 되는가?

  그 다음 phone_book에 요소가 현재 기준 요소보다 길이가 짧으면, prefix가 보장이 안되서, 전수 비교가 보장할 수가 없다.
  이에 이 케이스를 따로 둬서, prefix를 보장해주고, 전체 비교를 보장해주자.

for문을 이중으로 사용하기 때문에 prefix를 발견하면 바로 종료함으로 그나마 성능을 보장하려고 함.

🔧 코드

def solution(phone_book):
    answer = True
    for i in range(len(phone_book)):
        prefix = phone_book[i]
        prefix_len = len(prefix)
        for j in range(i+1,len(phone_book)):
            next_len = len(phone_book[j])
            if next_len <= prefix_len:
                target = phone_book[j][:next_len]
                if prefix[:next_len] == target:
                    return False
            else:
                target = phone_book[j][:prefix_len]
                if target == prefix:
                    return False
    return answer

💎 다른 사람의 풀이 참고

def solution(phone_book):
    answer = True
    hash_map = {}
    for phone_number in phone_book:
        hash_map[phone_number] = 1
    for phone_number in phone_book:
        temp = ""
        for number in phone_number:
            temp += number
            if temp in hash_map and temp != phone_number:
                answer = False
    return answer

많은 걸 배움. 내 코드는 이중 for문으로 최악의 경우 O(n^2)일 수도 있는데, 이 경우는 hashmap을 통해서 insert 최악 O(n), 이중 for문 O(n*20(전화번호 길이))로 성능적인 보장이 있고, Hashmap을 선언함으로써 temp로 조회된다는 것 자체가 key로 phone_number를 보장하면서, 실질적인 다른 번호라고 보장하는 아이디어가 좋았다고 생각함.

결론적으로, hashmap을 사용해서 성능 보존,그리고 phone_number를 보장하는 방식으로 조회를 생각했다는 점이 배울 점!