[네이버 코테 준비] 알고리즘 스터디 D - 3

핵심

• 완전 탐색으로 처음부터 쉽게 접근하기.
• print 많이 써서 디버깅해보기
• from collections import Counter
• sorted 함수 key에 lambda 식 활용하기 
  • https://gorokke.tistory.com/38

람다(lambda) 총 정리, key sort, key 정렬

• bfs 큐 사용할 때, 노드에 튜플 형태로 해당 노드의 depth까지 같이 저장해주면, 탐색 거리를 저장할 수 있다. 

 

1. 귤 고르기

처음에 배열만들어서 풀었는데, 이것보다 딕셔너리 쓰는 게 더 런타임이 줄어들었다. 

from collections import deque, Counter

def solution(k, tangerine):
    sizes = sorted(Counter(tangerine).items(), key=lambda x:x[1], reverse=True)
    # print(sizes)
    answer = 0 
    total_num = 0 
    for size, num in sizes:
        total_num += num
        answer +=1
        if total_num >= k : break
    return answer

https://velog.io/@isayaksh/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Programmers-%EA%B7%A4-%EA%B3%A0%EB%A5%B4%EA%B8%B0-Python

[알고리즘] Programmers 귤 고르기 #Python

 

2. 단어 변환

from collections import deque

def change_ok(begin, word):
    cnt = 0 
    for b, w in zip(begin, word):
        if b != w : cnt +=1
    if cnt == 1 : return True
    else: return False

def solution(begin, target, words):
    #최단 거리를 찾는 문제이므로 bfs 사용하기 
    queue = deque([(begin, 0)])
    if target not in words : return 0

    while queue:
        begin, depth = queue.popleft()
        for word in words:
            if change_ok(begin, word):
                if word == target : return depth+1
                queue.append((word, depth+1))
                
                
                
hit deque([('hot', 1)])
hot deque([('dot', 2), ('lot', 2)])
dot deque([('lot', 2), ('hot', 3), ('dog', 3), ('lot', 3)])
lot deque([('hot', 3), ('dog', 3), ('lot', 3), ('hot', 3), ('dot', 3), ('log', 3)])
hot deque([('dog', 3), ('lot', 3), ('hot', 3), ('dot', 3), ('log', 3), ('dot', 4), ('lot', 4)])

결국엔 dog -> cog으로 변환하고 바로 출력.

 

3. 타겟 넘버 

노드에 (계속 더해지는 결과값, 더해진 횟수)를 저장하는 것이 아이디어였음.

break의 기준은, 더해진 횟수가 numbers의 길이를 넘지 않도록

from collections import deque 

def solution(numbers, target):
    n = len(numbers)
    queue = deque([(0, -1)]) # sum, index
    answer = 0 
    while queue:
        total_sum, index = queue.popleft() # 0, 0
        if total_sum == target and index == n-1: 
            answer +=1
        try:
            queue.append((total_sum+ numbers[index+1], index+1))
            queue.append((total_sum- numbers[index+1], index+1))
        except: continue
        # print((total_sum, index), queue)
    return answer

 

4. 1차 셔틀버스