파이썬을 무기로, 코딩테스트 광탈을 면하자! 정리 (2)

프로그래머스의 파이썬을 무기로, 코딩테스트 광탈을 면하자!강의 5-7강을 정리한 글입니다.

---

5. 힙(Heap) 대표 문제 풀이: 더 맵게

문제: 더 맵게

• 최소, 최대 원소를 빠르게 꺼낼 수 있는 자료구조 → 힙!
• 복잡도: O(nlogn)

import heapq

def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)
    while True:
        min1 = heapq.heappop(scoville)
        if min1 >= K:
            break
        elif len(scoville) == 0:
            answer = -1
            break
        min2 = heapq.heappop(scoville)
        new_scoville = min1 + min2 * 2
        heapq.heappush(scoville, new_scoville)
        answer += 1
    return answer

6. 동적계획법(Dynamic Programming) 대표 문제 풀이: N으로 표현

문제: n으로 표현

• 적은 개수로 만들 수 있는 숫자를 조합하여 많은 개수로 만들 수 있는 숫자를 알 수 있다.
  • ex) 5 세 개로 만들 수 있는 숫자는 5 한 개, 두 개로 만든 숫자들을 사칙연산으로 조합한 수들이다.

→ 특정 개수로 만들 수 있는 숫자를 미리 만들어두고 조합해서 사칙연산을 하여 집합에 추가한다.

def solution(N, number):
    s = [set() for _ in range(8)] # 중복 제거를 위한 집합

    for i, x in enumerate(s, start = 1): # i=1부터 시작하게 만듦
        x.add(int(str(N) * i)) # ex) 5, 55, 555 등 먼저 넣음

    for i in range(len(s)):
        for j in range(i):
            for op1 in s[j]:
                for op2 in s[i - j - 1]:
                    s[i].add(op1 + op2)
                    s[i].add(op1 - op2)
                    s[i].add(op1 * op2)
                    if op2 != 0:
                        s[i].add(op1 / op2)
        if number in s[i]:
            answer = i + 1
            break
        else:
            answer = -1
    return answer

for-else 구문

• for 문이 break로 중간에 빠져나오지 않고 끝까지 실행되었을 경우 else문 실행!

7. 깊이/너비 우선 탐색(DFS/BFS) 대표 문제 풀이: 여행 경로

문제: 여행경로

• DFS: 연결된 노드들을 모두 방문하되, 방문한 노드에서 DFS를 끝낸 뒤(방문할 수 있는 곳을 모두 방문한 뒤) 이동
• 복잡도: O(nlogn)

def solution(tickets):
    routes = {}

    for t in tickets:
         routes[t[0]] = routes.get(t[0],[]) + [t[1]]
    for r in routes:
        routes[r].sort(reverse = True)

    stack = ["ICN"]
    path = []

    while len(stack) > 0:
        top = stack[-1]

        if top not in routes or len(routes[top]) == 0: #비행기표가 없거나 다 쓴 경우
            path.append(stack.pop())
        else:
            stack.append(routes[top][-1])
            routes[top].pop()

    return path[::-1] #역순으로 출력