[백준]230226 문제풀이

17298. 오큰수

import sys
N = int(sys.stdin.readline())
lst = list(map(int, sys.stdin.readline().split()))

stack = []
ans = []
for i in range(N - 1, -1, -1):
    if not stack:
        stack.append(lst[i])
    while stack:
        if stack[-1] <= lst[i]:
            stack.pop()
            if not stack:
                ans.append(-1)
        else:
            if stack:
                ans.append(stack[-1])
                break
            else:
                ans.append(-1)
    stack.append(lst[i])

ans = list(reversed(ans))
print(*ans)

스택을 이용한다는 것만 알면 쉽게 풀리는 문제(스택을 이용해야 하는지 몰라서 나에게는 어려웠음). 받은 리스트의 마지막에서부터 스택에 쌓아가며 현재 리스트의 마지막 수보다 크면 정답 리스트에 삽입, 작거나 같으면 pop하고 더이상 pop할 수 없으면 -1을 정답 리스트에 삽입한다. 해당 과정이 끝나면 스택에 꼭 리스트 마지막 값을 집어넣어주는게 뽀인트

1325. 효율적인 해킹

from collections import deque
import sys

def bfs():
    cnt = 0
    while queue:
        now = queue.popleft()
        cnt += 1
        for n in adj[now]:
            if not visited[n]:
                visited[n] = True
                queue.append(n)
    return cnt

N, M = map(int, sys.stdin.readline().split())
adj = [[] for _ in range(N + 1)]
hacking = [0] * (N + 1)
for i in range(M):
    a, b = map(int, sys.stdin.readline().split())
    adj[b].append(a)

for start in range(1, N + 1):
    visited = [False] * (N + 1)
    visited[start] = True
    queue = deque([start])
    hacking[start] = bfs()

ans_list = []
temp = 0
for i in range(1, N + 1):
    if hacking[i] > temp:
        ans_list.clear()
        temp = hacking[i]
        ans_list.append(i)
    elif hacking[i] == temp:
        ans_list.append(i)

print(*ans_list)

dfs, bfs 모두 가능하다고 하는데 재귀 dfs를 했을 때 계속 에러가 떠서 bfs로 풀었다. 신뢰하는 컴퓨터가 자식노드, 신뢰받는 컴퓨터가 부모 노드인 것으로 설정하고 for문으로 1~N번 노드를 돌면서 각 노드에 대한 자식 노드 수를 저장했다. 저장된 자식 노드 수를 순회하며 가장 많은 자식 노드 수를 가진 값들을 찾아냈다.

12851. 숨바꼭질 2

from collections import deque

N, K = map(int, input().split())
if N == K:
    print(0)
    print(1)
if N < K:
    visited = [[0, 1] for _ in range(100001)]
    queue = deque([N])

    while queue:
        now = queue.popleft()
        if now == K:
            break
        if 0 <= now + 1 <= 100000:
            if not visited[now + 1][0]:
                visited[now + 1][0] = visited[now][0] + 1
                visited[now + 1][1] = visited[now][1]
                queue.append(now + 1)
            elif visited[now + 1][0] == visited[now][0] + 1:
                visited[now + 1][1] += visited[now][1]
        if 0 <= now - 1 <= 100000:
            if not visited[now - 1][0]:
                visited[now - 1][0] = visited[now][0] + 1
                visited[now - 1][1] = visited[now][1]
                queue.append(now - 1)
            elif visited[now - 1][0] == visited[now][0] + 1:
                visited[now - 1][1] += visited[now][1]
        if 0 <= now * 2 <= 100000:
            if not visited[now * 2][0]:
                visited[now * 2][0] = visited[now][0] + 1
                visited[now * 2][1] = visited[now][1]
                queue.append(now * 2)
            elif visited[now * 2][0] == visited[now][0] + 1:
                visited[now * 2][1] += visited[now][1]

    print(visited[K][0])
    print(visited[K][1])

if N > K:
    print(N - K)
    print(1)

정답에 도달하기 위해 거치는 값들에 도달하는 경우의 수를 저장해야 한다는 생각은 했는데, 도저히 방법이 떠오르지 않아 거의다 구글링해서 푼 문제... 큐에 넣을 값에 방문한 노드들을 저장하려 했으나 hashable하지 않은 값은 요소가 될 수 없다고 하여 막막했다. 이럴 때는 고정돼있는 visited를 이용하면 값도 쉽게 바꿀 수 있고 시간복잡도도 최소화할 수 있기 때문에 앞으로도 그래프 탐색에서 필요한 값들이 많으면 visited를 적극적으로 활용해봐야겠다.