7/27 미경이 스터디

코변·2022년 7월 27일

올바른 괄호

from collections import deque
def solution(s):
    check_right_parentheses = deque(list(s))
    last_parenth = []
    while check_right_parentheses:
        cur_parenth = check_right_parentheses.popleft()
        if len(last_parenth) == 0 and cur_parenth == ')':
            return False
        elif len(last_parenth) !=0 and cur_parenth != last_parenth[-1]:
            last_parenth.pop()
        else:
            last_parenth.append(cur_parenth)
            
    if len(last_parenth) > 0:
        return False
    return True

내가 이해한 룰

괄호로 이루어진 리스트가 주어진다.
이 괄호가 올바른 괄호 형태로 짝지어져 있는지 검사한다.
생각해봐야할 조건들
2-1. ')'괄호가 처음부터 나오는 경우
2-2. '(',')','(' 이와 같이 갯수가 맞지 않은경우
2-3. ')' '(' ')', '(' 이와같이 갯수는 맞으나 짝이 맺어져 있지 않은 경우

문제풀이

2-1 조건을 고려

이전 값을 저장해둔 스택의 길이가 0일 때 닫는 괄호가 나온다면 바로 False를 반환하도록 했다.

2-2, 2-3 조건을 고려

짝이 맞으면 이전값 스택에서 pop을 해준다.
짝이 맞지 않으면 스택에 담는다.
모든 괄호를 다 뽑아냈다면 while문을 종료하고
종료한 후에 이전값을 담는 스택에 값이 남아 있다면 False를
스택에 값이 없다면 True를 반환한다.

네트워크

def dfs(visited, computers, node):
    if visited[node] == 0:
        visited[node] = 1
        for idx, is_network in enumerate(computers[node]):
            if visited[idx] == 0 and is_network:
                dfs(visited, computers, idx)
        return True
    return False

def solution(n, computers):
    cnt = 0
    visited = [0] * n
    for i in range(n):
        if dfs(visited, computers, i):
            cnt+=1
    return cnt

내가 이해한 룰

컴퓨터가 서로 이어져 있다면 같은 네트워크를 공유하고 있는것이다.
컴퓨터는 자기 자신에 대해서 네트워크를 공유하고 있다.
네트워크에 대한 정보가 2차원 리스트로 주어진다.
네트워크들의 갯수를 구하라

문제풀이

bfs로 풀려고 했으나 내가 dfs보다 bfs를 더 선호하는 것 같아서 dfs로 풀어보았다.(연습을 위해)
컴퓨터 갯수가 주어지기 때문에 이를 활용해서 visited를 초기화 해준다.
dfs 로직을 분리하여 함수로 만들어주고 재귀 함수로 구현해준다.
재귀함수는 들어온 컴퓨터의 인덱스 값을 토대로 연결되어 있는 모든 값들을 순회하면서 visited의 값을 1로 바꾸어준다.
한번 dfs를 거치고 나면 연결된 모든 컴퓨터들의 visited 값은 1이 되므로 연결되지 않은 값들만 dfs로직 안을로 들어오게 된다.
따라서 dfs가 true를 반환할 때만 cnt값을 1올려주면 네트워크의 수를 구할 수 있다.

더 맵게

import heapq
def solution(scoville, K):
    cnt = 0
    heapq.heapify(scoville)
    while scoville:
        first = heapq.heappop(scoville)
        if first >= K: return cnt
        if len(scoville) == 0: return -1
        second = heapq.heappop(scoville)
        new_food = (first + (second*2))
        scoville.append(new_food)
        cnt+=1
    return -1