[프로그래머스] 해시 - 전화번호 목록

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

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

 

 

 

[내 풀이]

 

첫번째 풀이)

 

 

접두사의 의미를 모르고 맨 처음에 not in 과 in 을 이용해서 반복문을 돌려서 자꾸 에러가 났다.

특히 문자열이 박힌 list를 굳이 int를 만들어서 sort하려는 행위가 문제를 제대로 이해한게 아니라는 생각이 든다.

바로 string값에서 sort를 해주고 앞뒤만 비교해주는 것이 왜 정답이 될 수 있는지에 대해 생각을 못했던 것 같다.

수능수학과 같은 느낌이다. 코테 또한 문제를 잘 읽고 예시도 주니까 검증까지 생각하면서 코드 짜자.

 

두번째 풀이)

def solution(phone_book):
    
    answer = True
    
    if len(phone_book)==1:
        return answer
    else:
        temp = sorted(phone_book)
        
        while len(temp)>1:
            head = temp.pop(0)
            for i in range(len(temp)):
                if head == temp[i][:len(head)]:
                    answer = False
                    break
        
        return answer

 

세번째 풀이)

def solution(phone_book):
    length = len(phone_book)
    
    phone_book.sort()
    for i in range(length-1):
        suffix = phone_book[i]
        for number in phone_book[(i+1):]:
            if number[:len(suffix)] == suffix:
                return False
    return True

 

두 풀이 모두 효율성 측면에서 걸렸다.

 

수정 풀이)

def solution(phone_book):
    phone_book.sort()
    for a in range(len(phone_book)-1):
        if phone_book[a] in phone_book[a+1] :
            return False
    return True

테케 13에서 걸림.

3, 23 과 같은 경우

3이 23에 포함되기 때문에 넘어가지만, 실제로 접두어는 아니기 때문에 문제 정답이 될 수 없음.

 

나 같은 경우는 오히려, 12, 384, 1249 과 같이 한 타임 뛰어있는 들어있으면 못잡지 않나?

 

sort의 결과물에 대한 이해도 부족

아스키 코드로 문자열의 크기가 아니라 맨 앞자리부터 소팅을 시작하기 때문에

위와 같은 리스트가 만들어 질리는 없음.

 

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

다음과 같이 in을 쓰지말고, 슬라이싱을 해줘서 같다로 조건문 걸어주면 통과

 

[해시를 이용한 풀이]

def solution(phone_book):
    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:
                return False
    return True

가장 문제출제의도대로 잘 푼듯.

해시도 해시지만 temp에 number 더해가면서 접두사 파악해주는 의도도 창의적이었다.

 

 

[참고1]

zip과 startswith이라는 내장함수를 이용해서 굉장히 깔끔하게 짠 것 같다.

 

[참고2]

def solution(phone_book):
    for i in range(len(phone_book)):
        pivot = phone_book[i] 
        for j in range(i+1, len(phone_book)):
            strlen = min(len(pivot), len(phone_book[j]))
            if pivot[:strlen] == phone_book[j][:strlen]: 
                return False 
            return True

댓글에 있는 코드인데 이것도 이중반복문을 이용해서 읽기 편한 것 같다.

 

시간복잡도 측면으로 봤을때 앞선 코드들보다 좋지 못하다.

자료구조나 알고리즘 측면으로 시간복잡도를 줄일 수도 있겠지만,

문제를 어떻게 최소한의 리소스를 들여서 해결할지, 문제를 해결하는 아이디어 측면에서도 시간복잡도를 줄일 수도 있겠다는 생각이 들었다.