[5월 1주차] 3문제 풀이

[완전탐색] 전력망을 둘로 나누기 (Lv.2)

접근 방식

n의 크기가 크지 않고 트리의 크기를 구하는 시간복잡도가 O(N)이라 완전탐색으로 풀어도 되는 문제라 판단했다.
트리의 사이즈를 구하는 함수를 만들고, 모든 링크를 끊어 그 링크에 해당하는 노드를 포함한 각 트리의 사이즈를 구해 계산했다.

정답 코드

class Node:
    def __init__(self, num):
        self.num = num
        self.connected = []

class Tree:
    def __init__(self, links):
        self.nodes = {}
        for link in links:
            v1, v2 = link
            if v1 not in self.nodes:
                self.nodes[v1] = Node(v1)
            if v2 not in self.nodes:
                self.nodes[v2] = Node(v2)
            self.nodes[v1].connected.append(v2)
            self.nodes[v2].connected.append(v1)
    def get_tree_size(self, start, visited):
        visited.add(start)
        size = 1
        if start in self.nodes:
            for neighbor in self.nodes[start].connected:
                if neighbor not in visited:
                    size += self.get_tree_size(neighbor, visited)
        return size

def solution(n, wires):
    answer = 1000

    for wire in wires:
        tree = Tree([w for w in wires if w != wire])
        start1, start2 = wire
        visited = set()
        size1 = tree.get_tree_size(start1, visited)
        size2 = tree.get_tree_size(start2, visited)
        answer = min(answer, abs(size1-size2))

    return answer

배운 점

트리 구조 자체는 자주 만들게 될 거라 자주 만들어서 익혀두면 좋을 것 같다.

---

[문자열] 괄호 변환 (Lv.2)

접근 방식

문제에서 제공하는 조건을 충실히 이행하는 재귀함수를 구현하면 되는 문제다.

정답 코드

def func(w):
    if not w:
        return ''
    res = ''
    stack = []
    cnt = [0, 0]
    nice = True
    for i in w:
        idx = 0 if i == '(' else 1
        stack.append(i)
        cnt[idx] += 1 
        # 올바른 괄호 문자열인지 파악
        if cnt[0] < cnt[1]:
            nice = False
        # 균형잡힌 괄호 문자열이 됐을 때 break
        if cnt[0] == cnt[1]:
            break
    u = ''.join(stack)
    v = w[sum(cnt):]
    
    # 3번 수행
    if nice:
        res += u + func(v)
    # 4번 수행
    else:
        temp = ''
        for i in u[1:-1]:
            if i == '(':
                temp += ')'
            else:
                temp += '('
        res += '(' + func(v) + ')' + temp
    

    return res

def solution(p):
    return func(p)

배운 점

문제를 보고 원래 아는 방법대로 풀지 말고 문제를 제대로 읽고 조건에 맞춰서 코드를 짜도록 하자

---

[구현, 수학] N개의 최소공배수 (Lv.2)

접근 방식

정답 코드

def lcm(num1, num2):
    a = max(num1, num2)
    b = min(num1, num2)
    res = a
    while True:
        if res % b == 0:
            return res
        res += a
    
def solution(arr):
    if len(arr) == 1:
        return arr[0]
    answer = lcm(arr[0], arr[1])
    for i in range(2, len(arr)):
        answer = lcm(answer, arr[i])
        
    return answer

배운 점

$a \times b = GCD(a, b) \times LCM(a, b)$

# 1
import math
result = math.gcd(a, b)
# 2
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a