프로그래머스/ 전화번호 목록

문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/42577#

Brute-Force : O(n^2)으로 해결 가능. 하지만 문제 조건에서 n<1000000라고 제시했으므로 위의 시간복잡도라면 매우 exponential하다.

추론

결국 "존재하냐, 안하냐"의 문제이므로 search space에서 answer를 찾아낸다. 그렇다면 어떻게 search space를 생성하고 탐색할까? 한 자리수마다 탐색해서 분류로 묶어주고 재귀를 이용한다면 해결 가능하지 않을까? 그리고 만약 "찾는다"의 조건문만 있으면 문제 해결 가능.

따라서 분류로 묶어줄 n, 자리수를 나타내는 i, search space인 book을 parameter로 phone_search 함수 생성 ( 주먹구구 식 )

def phone_search(n,i,book):
    if i!=1 and len(book)==1 :
        return True
    tmp = {}
    result= ""
    for p in book :
        if len(p)==i :
            result = p
            continue
        if result == p[:i] :
            return False
        if p[i-1] not in tmp :
            tmp[p[i-1]]=[p]
        else :
            tmp[p[i-1]].append(p)
    for n_p in tmp :
        if not phone_search(n*10+int(n_p),i+1,tmp[n_p]):
            return False
    return True

def solution(phone_book):
    answer = True
    phone_book.sort(key=len)
    for n in range(1,10) :
        if not phone_search(n,1,phone_book) :
            return False
    return answer

정확성, 효율성 둘 다 테스트 케이스 3에서 실패

결국 찾기만 하면 된다! 있기만 하면 된다! 문제의 특성을 적극적으로 이용하자.

1. sort, sorted의 문자열 정렬 방식과 key를 부여해 정렬 기준 변경 방식
   정렬 논리 : int는 크기 순서대로 , str은 string의 index에 대한 순차적인 정렬 적용. 숫자 크기, str 길이 X. But key를 통한 적용 가능.
   +) "여러 개의 value를 가진 객체" index 기준으로 순차적인 정렬

sort( list, key = function, reverse= bool )

reverse=True : 내림차순
reverse=False : 오름차순

key

ex1. list.sort(key = lambda x:x[1] )
-> list의 element를 기준으로 두 번째 index에 대해 정렬

ex2. list.sort(key = lambda (x:x[2], -x[1] ))
-> list의 element를 기준으로 세 번째 index에 대해 우선 정렬하고 두 번째 index에 대해 내림차순으로 정렬

ex3. list.sort(key=len) # list is string
-> string을 가지는 list의 길이를 기준으로 정렬

ex4. 임의로 순서 부여 정렬
priority_dict = {4:0, 2:1, 3:2, 1:3}
list = [4,1,3,4,1,2,4,3,4,1,2,1,2,1,1]
list.sort(key = lambda x: priority_dict[x])
-> 4,2,3,1의 순서로 정렬, [4,4,4,4,3,3,2,2,2,1,1,1,1,1,1]

ex5. 딕셔너리 key 정렬
sorted(priority_dict.items())
-> key 기준 정렬 [(1,3), (2,1), (3,2), (4,0)]

ex6. 딕셔너리 value 정렬
sorted(priority_dict.values())
-> [0,1,2,3]
sorted(priority_dict.items(),key = lambda x: x[1])
-> [(4,0),(2,1),(3,2),(1,3)]

dictionary 함수

1. dictionary.keys() : key 뽑아내기-> list로 한 번 감싸줘라.
2. dictionary.values() : 값 뽑아내기. 원래 순서는 보장되지 않는다. keys()함수와는 순서가 보장된다.
3. dictionary.items() : key,value 쌍으로 뽑아내기
4. "Key" in dictionary : key 내부의 원소에서 찾는다.