코딩 테스트 문제 풀이

문제풀이

전력망을 둘로 나누기

from collections import deque
def solution(n, wires):
    answer = 0
    graph = [[] for _ in range(n+1)]
    for a, b in wires:
        graph[a].append(b)
        graph[b].append(a)
    
    def bfs(start):
        queue = deque([start])
        visited = [0]*(n+1)
        visited[start] = 1
        cnt = 1
        while queue:
            v = queue.popleft()
            for i in graph[v]:
                if not visited[i]:
                    queue.append(i)
                    visited[i] = 1
                    cnt += 1
        return cnt
    
    answer = n
    for a, b in wires:
        graph[a].remove(b)
        graph[b].remove(a)
        
        answer = min(answer, abs(bfs(a) - bfs(b)))
        
        graph[a].append(b)
        graph[b].append(a)
    return answer

< 풀이 과정 >
bfs를 이용하여 문제를 풀이하였다.
bfs 알고리즘 구현을 위해 deque를 이용.
1. 0~n의 노드를 가진 graph를 생성하여 양방향 간선을 생성해주고, bfs를 이용하여 시작점으로 부터 연결되어 있는 노드 수를 계산해내는 함수를 생성한다.
2. wires 시작점, 도착지점을 a, b로 구분하여 for문 만큼 순회 후 다시 처음부터 remove해주면서 최소 answer를 찾아준다.

택배상자

def solution(order):
    answer = 0
    idx = 1
    container = []
    while idx != len(order) + 1:
        container.append(idx)
        while container[-1] == order[answer]:
            answer += 1
            container.pop()
            if len(container) == 0:
                break
        idx += 1
    return answer

< 풀이 과정 >
생각을 좀 오래하고 푼 문제. 간단히 생각해보면 stack으로 빈 리스트를 만들어 order내 물품 리스트의 인덱스만큼 값을 추가해준다.
각 인덱스 별로 order[상자수] == stack[가장 처음 넣은 물품 리스트] 인 경우 택배 보내는 상자 개수를 += 1진행하고 물품 리스트 내 가장 처음 넣은 물품 리스트를 삭제하여 이어서 진행해준다.

문자열 압축

def solution(s):
    answer = []
    if len(s) == 1:
        return 1
    for i in range(1, len(s)//2+1):
        result = ''
        cnt = 1
        check = s[:i]
        for j in range(i, len(s)+i, i):
            if check == s[j:j+i]:
                cnt += 1
            else:
                if cnt != 1:
                    result += str(cnt) + check
                else:
                    result += check
                check = s[j:j+i]
                cnt = 1
        answer.append(len(result))
    return min(answer)

하노이의 탑

def hanoi(n, start, end, mid):
    if n == 1:
        return [[start, end]]
    else:
        result = []
        result += hanoi(n-1, start, mid, end)
        result += [[start, end]]
        result += hanoi(n-1, mid, end, start)
        
    return result
def solution(n):
    answer = hanoi(n, 1, 3, 2)
    return answer