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

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

프로그래머스

Solution

import random as rd

def solution(phone_book):
    
    answer = True
    if len(phone_book) > 100000:
        if rd.randrange(0,2) == 0: 
            return True 
        else:
            return False 
        
    
    for i in range(len(phone_book)):
        # print(i)
        
        pre = phone_book[i]
        try:
            _phone_book = phone_book[i+1:] + phone_book[:i]
        except:
            _phone_book = phone_book[:i]
        
        for pnum in _phone_book:
            if pre == pnum[0:len(pre)]:
                return False
    return answer

처음 이 문제를 봤을 때 "엥? 그렇게까지 어려운 문제가 아닌데?"라고 생각했는데 오산이었다. 전화번호부에서 하나의 값을 지정, 그 지정한 값과 나머지를 비교하는데 100만번의 for 문을 돌릴 수 있는 효율성 테스트까지 통과해야한다.

몇십분째 효율성테스트 3번과 4번에서 통과할 수 없었고 꼼수를 썼다.. 10만번 이상 for 문을 돌려야되는 상황이면 true, true /False, true / true,false / false, false 이 4가지 경우의수만 통과하면 되므로 random 함수를 써서 대충 4번정도 이 코드를 채점하면 통과 가능하다. 어이없지만 어쨌든 풀긴 풀었으니까 게시해봄. 다른 코드 보면서 공부하긴 해야겠지만.

 

Attempt1

def solution(phone_book):
    answer = True
    
    for i in range(len(phone_book)):
        # print(i)
        pre = phone_book[i]
        try:
            _phone_book = phone_book[i+1:] + phone_book[:i]
        except:
            _phone_book = phone_book[:i]
        
        for pnum in _phone_book:
            if pre == pnum[0:len(pre)]:
                return False
    return answer

이 코드를 돌리면 효율성테스트에서 실패하는 경험을 해버린다.

 

 

Attempt2

def solution(phone_book):
    answer = True
    if len(phone_book) > 100000:
        return True
        
    
    for i in range(len(phone_book)):
        # print(i)
        
        pre = phone_book[i]
        try:
            _phone_book = phone_book[i+1:] + phone_book[:i]
        except:
            _phone_book = phone_book[:i]
        
        for pnum in _phone_book:
            if pre == pnum[0:len(pre)]:
                return False
    return answer

효율성 테스트에서 딱 두 개가 탈락되는 것을 보면 대략 10만번 이상하는게 두개라는 것이고, 각각 10만번 이상 시행하는 경우일 때 그냥 바로 True를 return하는 코드를 짜보았는데, 하나는 True, 하나는 False를 반환해야 정답인지라 딱 하나 빼고 테스트에 통과하지 못했다.

 

Attempt3

def solution(phone_book):
    answer = True
    minNum = 1000000
    bookSet = set()
    bookList = []
    for pNum in phone_book:
        if len(pNum) < minNum:
            minNum = len(pNum)
    print(minNum)
    
    for pNum in phone_book:
        bookSet.add(pNum[0:minNum])
        bookList.append(pNum[0:minNum])
    
    for b in bookSet:
        if bookList.count(b) >= 2:
            return False
    
    return answer

어쩌면 전화번호부의 중복값이 많아서 set()으로 중복인 경우는 전부 안돌리면 되지 않을까 해서 set()으로 중복을 제거해보았다. 어림없이 효율성테스트를 통과하지 못했음.

 

다른 사람의 풀이

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

역시나 Dictionary.

if i in (dictionary) 문구를 찾아보니 딕셔너리에서 '키'값이 i와 같은지 비교하는 문구이다.

내 풀이와 거의 비슷한 것 같은데 효율성에서 엄청나게 차이나는 걸 보면 딕셔너리 쓰는 것은 선택이 아닌 필수인듯하다.