[python] [프로그래머스] 전화번호 목록, 의상 (해시 문제)

1. 전화번호 목록 (https://school.programmers.co.kr/learn/courses/30/lessons/42577)

(레벨 2)

• 처음에는 아래처럼 풀었는데 시간초과가 나와서 쓸 수 없는 코드라고 판단하여 다른사람의 답을 찾아봤다
• 일단 아이디어는 pivot을 설정하는 것처럼 i를 기준으로 두고 for loop을 하나 더 돌려 i+1부터 마지막까지의 전화번호를 확인한다
• 이 때, i 번째 전화번호와 j 번째 전화번호의 첫 숫자들이 같으면 False, 아니라면 True를 반환한다
• 아무래도 for loop을 두 번 사용하고 slicing까지 사용해서 시간 초과가 난 것 같다

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

• 그래서 찾아봤더니 python에는 .startswith()이라는 빌트인 메소드가 존재했다 ;;
• 아이디어는 같고, 달라진 점이라면 sorted()를 사용하여 첫 숫자들이 같은 애들끼리 근처에 존재하게 해주었다
• 한눈에 봐도 시간복잡도가 줄어들었다는 것을 알 수 있다

phone_book = sorted(phone_book)
ans = True
for i in range(len(phone_book)-1):
    if phone_book[i+1].startswith(phone_book[i]):
        ans = False
return ans

---

2. 의상 (https://school.programmers.co.kr/learn/courses/30/lessons/42578#)

(레벨 2)

• https://beomcoder.tistory.com/45

프로그래머스 해시 '위장' 파이썬 풀이

• 위 블로그를 참고했다
• 일단 key = 카테고리, value = 의상 리스트 로 만들어주고 (나는 defaultdict 사용)
• 의상을 하나씩 입는 경우도 있기 때문에 투명한 옷이 있다고 가정하고 (count *= (len(x) + 1) 의 +1 이 투명한 옷) 확률을 계산함
• 예를들어 (선글라스, 상의) (안경, 하의) 이렇게 있었다면 (선글라스, 상의, 투명한 옷) (안경, 하의, 투명한 옷) 으로 해서 둘의 길이를 곱함 --> 그럼 모든 경우의 수가 나옴
• 그리고 마지만 return 에서는 투명한 옷 x 투명한 옷(= 아무것도 안입은) 경우를 빼주고 return

from collections import defaultdict

def solution(clothes):
    all_clo = defaultdict(list)
    for i in range(len(clothes)):
        all_clo[clothes[i][1]] += [clothes[i][0]]
        
    count = 1
    for v in all_clo.values():
        count *= (len(v) + 1)
        
    return count - 1