[프로그래머스] 해시-전화번호 목록 (level.1)

 

문제 링크

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

코딩테스트 연습 - 전화번호 목록

 

나의풀이

1. 전화번호 목록에 있는 전화번호들을 하나씩 추출
2. 추출된 전화번호 내에서 한글자씩 뽑아서 n에 저장
3. n이 추출된전화번호와 같진 않지만, 전화번호부에 존재하는지 확인
4. (추가) dic 구성

초반에는 이렇게만 풀었었다. 근데 효율성 테스트에서 시간초과가 뜨면서 에러가 났다. 어떻게하면 시간 초과를 줄일 수 있을까 고민하다가, 인터넷의 도움을 받앗다. 왜 문제가 해시 알고리즘일까? 생각해보니, dic 을 활용해서 효율성을 높일 수 있었다. 전화번호를 dic에 key값으로 넣어서 key값들을 비교함으로써 (사실상 내가 짠 코드와 방법은 같음, dic만 활용할 뿐) 효율을 높였다.

# 초반에 짠 코드 (효율성 테스트 시간 초과)
# def solution(phone_book):
#     for number in phone_book:
#         n = ""
#         for num in number:
#             n += num
#             if n in phone_book and n!=number:
#                 return False
#     return True

def solution(phone_book):
    dic = {}
    for i in range(len(phone_book)):
        dic[phone_book[i]] = 1 #key값만 쓸꺼니까 그냥 value는 전부 1넣어줌
    for number in phone_book:
        n = ""
        for num in number:
            n += num
            if n in dic and n!=number:
                return False
    return True

 

다른 사람 풀이

https://programmers.co.kr/learn/courses/30/lessons/42577/solution_groups?language=python3 

프로그래머스

내가 푼 풀이가 많은 좋아요를 받은 풀이 중 하나였다. 기분이 좋다. 역시 사람들은 생각하는 방식이 다 같은건가 히히 최대한 해시 알고리즘을 이용해서 풀려고 노력한 점이 이런 결과를 낸것같다.

나랑 같이 스터디하는 오빠는 아래와 같은 코드로 짯다. 해시알고리즘을 사용하진 않았지만 아이디어가 좋았다. startswith 기억하자!

startswith 함수를 이용한 코드 (좋아요수가 가장 많은 코드이기도 함)

from itertools import permutations
def solution(phone_book):
    answer = True
    for a in list(permutations(phone_book,2)):
        if a[1].startswith(a[0]): answer=False
        
    return answer

 

combination, sorted(key = len ) 이용한 코드

from itertools import combinations as c
def solution(phoneBook):
    answer = True
    sortedPB = sorted(phoneBook, key= len)
    for (a,b) in c( sortedPB,2):
        if a == b[:len(a)]:
            answer = False
    return answer

key=len...? 단어 길이순으로 정렬할수 있는 방법이다. 내가 초반에 이렇게 하고싶었는데,,, 정렬을 이렇게 할수있다니 혁신적이다.. 기억해두자