스택/큐 실전 패턴과 디버깅 포인트

스택/큐 문제는 컴파일 에러보다 조용한 오답이 더 자주 나옵니다. 그래서 코드가 실행되는데도 결과가 틀려서 막히는 경우가 많습니다. 이럴 때는 정답 코드 찾기보다 상태 추적 기준을 우선 세우는 편이 빠릅니다.

이 파트에서는 상태가 정상적으로 변하고 있는지를 확인하는 디버깅 루틴을 우선 익힙니다. push/pop 순서, 빈 구조 처리, 방문 체크 시점을 중심으로 설명합니다.

핵심 패턴 해설

실전에서는 자료구조 이름보다 상태가 어떻게 바뀌는지를 읽는 힘이 더 중요합니다. 지금 푸는 문제를 기준으로 현재 상태 변수를 우선 적고 아래 개념과 연결해 보세요.

상태 전이는 현재 정보가 다음 단계 정보로 바뀌는 흐름입니다. 한 번의 연산 후 상태 변수 집합이 어떻게 갱신되는지를 함수처럼 보는 관점입니다. BFS에서 u를 꺼내 이웃 v를 넣으면 큐 내용과 거리 배열이 동시에 바뀌는 장면이 전형적인 상태 전이입니다.

불변 조건(invariant)은 반복 중에도 항상 지켜져야 하는 약속입니다. 정확히는 루프 반복 전후에 참이어야 하는 논리 조건으로, 정당성 검증의 기준이 됩니다. 괄호 검사에서는 스택에 아직 닫히지 않은 여는 괄호만 남아 있어야 한다는 조건이 불변식입니다.

관찰 로그 포인트는 디버깅할 때 매 단계 확인할 최소 항목입니다. 상태 추적에 필요한 변수 집합(top/front/size/visited)을 고정해 기록하는 방식입니다. 큐 문제에서 처음 몇 스텝의 front, size, dist만 출력해도 오답이 시작되는 지점을 빠르게 찾을 수 있습니다.

스택/큐 실전 장애 패턴과 연결하기

스택/큐 버그는 실행은 되지만 결과가 조용히 틀리는 경우가 많습니다.
예외가 터지지 않아 원인 추적이 늦어지는 것이 더 큰 문제입니다.

따라서 구현 시점부터 검증 가능한 상태를 남기는 습관이 필요합니다.
예: 현재 크기, front/top 값, 처리된 원소 수를 로그로 고정. 지금 코드에 front/top/size 출력 한 줄을 넣고 첫 5스텝만 실행해 보세요.

순회 시나리오 테스트로 빠르게 검증하기

학습 효율을 높이려면 오답 -> 디버깅 -> 교정 -> 검증 순서로 로그를 남기면서 진행하는 것이 가장 빠릅니다.

BFS 최소 거리 예제로 상태 전이를 간단히 따라가 봅니다.

그래프: 0-1, 0-2, 1-3
시작 정점: 0

큐 시작 상태는 [0], dist[0]=0입니다.
0을 꺼내 이웃 1,2를 넣고 거리를 1로 기록합니다.
1을 꺼내 3을 넣고 거리를 2로 기록합니다.
방문 체크 시점을 enqueue 시점으로 고정해야 중복 삽입을 막을 수 있습니다.

괄호 유효성 검사(스택)

문제 의도: 스택으로 괄호 매칭의 상태 전이를 검증합니다.
입력 예시: s="({[]})", s="([)]"
출력 예시: true, false push는 여는 괄호를 쌓고, pop은 닫는 괄호를 만날 때 짝을 확인하며 꺼냅니다.

main.cpp

#include <iostream>
#include <stack>
using namespace std;

bool isValidParentheses(const string& s) {
    stack<char> st;

    for (char ch : s) {
        if (ch == '(' || ch == '[' || ch == '{') {
            st.push(ch);
        } else {
            if (st.empty()) return false;
            char open = st.top();
            if (ch == ')' && open != '(') return false;
            if (ch == ']' && open != '[') return false;
            if (ch == '}' && open != '{') return false;
            st.pop();
        }
    }
    return st.empty();
}

int main() {
    cout << boolalpha << isValidParentheses("([]{})") << "\n";
    cout << boolalpha << isValidParentheses("([)]") << "\n";
    return 0;
}

Main.java

import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
    static boolean isValidParentheses(String s) {
        Deque<Character> st = new ArrayDeque<>();

        for (char ch : s.toCharArray()) {
            if (ch == '(' || ch == '[' || ch == '{') {
                st.push(ch);
            } else {
                if (st.isEmpty()) return false;
                char open = st.peek();
                if (ch == ')' && open != '(') return false;
                if (ch == ']' && open != '[') return false;
                if (ch == '}' && open != '{') return false;
                st.pop();
            }
        }
        return st.isEmpty();
    }

    public static void main(String[] args) {
        System.out.println(isValidParentheses("([]{})"));
        System.out.println(isValidParentheses("([)]"));
    }
}

main.py

def is_valid_parentheses(s):
    st = []

    for ch in s:
        if ch in "([{":
            st.append(ch)
        else:
            if not st:
                return False
            open_bracket = st[-1]
            if ch == ")" and open_bracket != "(":
                return False
            if ch == "]" and open_bracket != "[":
                return False
            if ch == "}" and open_bracket != "{":
                return False
            st.pop()

    return len(st) == 0

print(is_valid_parentheses("([]{})"))  # True
print(is_valid_parentheses("([)]"))    # False

main.rs

fn is_valid_parentheses(s: &str) -> bool {
    let mut st: Vec<char> = Vec::new();

    for ch in s.chars() {
        if ch == '(' || ch == '[' || ch == '{' {
            st.push(ch);
        } else {
            if st.is_empty() {
                return false;
            }
            let open = st[st.len() - 1];
            if ch == ')' && open != '(' {
                return false;
            }
            if ch == ']' && open != '[' {
                return false;
            }
            if ch == '}' && open != '{' {
                return false;
            }
            st.pop();
        }
    }
    st.is_empty()
}

fn main() {
    println!("{}", is_valid_parentheses("([]{})"));
    println!("{}", is_valid_parentheses("([)]"));
}

스택/큐 실전 확인 불변식 초기 확인

여는 괄호는 push, 닫는 괄호는 top 비교 후 pop이라는 규칙이 핵심입니다.
중간 불일치를 즉시 실패 처리하면 불필요한 연산을 줄일 수 있습니다.
마지막에 스택이 비어 있어야 완전한 매칭입니다.

평균 시간복잡도: O(N)
최악 시간복잡도: O(N)
공간복잡도: O(N)

작업 큐 시뮬레이션

문제 의도: 큐를 이용해 작업 처리 순서와 누적 시간을 시뮬레이션합니다.
입력 예시: jobs=[("A",3),("B",1),("C",2)]
출력 예시: 작업별 완료 시점 리스트 큐는 먼저 들어온 작업을 먼저 처리하므로 처리 순서가 코드에서 바로 드러납니다.

main.cpp

#include <iostream>
#include <string>
#include <utility>
#include <vector>
using namespace std;

vector<pair<string, int>> processJobs(const vector<pair<string, int>>& jobs) {
    vector<pair<string, int>> q = jobs;
    vector<pair<string, int>> done;
    int head = 0;
    int time = 0;

    while (head < static_cast<int>(q.size())) {
        string name = q[head].first;
        int cost = q[head].second;
        head += 1;
        time += cost;
        done.push_back({name, time});
    }
    return done;
}

int main() {
    vector<pair<string, int>> jobs = {{"A", 3}, {"B", 2}, {"C", 5}};
    vector<pair<string, int>> done = processJobs(jobs);
    for (int i = 0; i < static_cast<int>(done.size()); ++i) {
        cout << "(" << done[i].first << ", " << done[i].second << ") ";
    }
    cout << "\n";
    return 0;
}

Main.java

import java.util.ArrayList;
import java.util.List;

public class Main {
    static List<String> processJobs(String[] names, int[] costs) {
        List<String> done = new ArrayList<>();
        int head = 0;
        int time = 0;

        while (head < names.length) {
            time += costs[head];
            done.add("(" + names[head] + ", " + time + ")");
            head += 1;
        }
        return done;
    }

    public static void main(String[] args) {
        String[] names = {"A", "B", "C"};
        int[] costs = {3, 2, 5};
        System.out.println(processJobs(names, costs));
    }
}

main.py

def process_jobs(jobs):
    q = list(jobs)
    done = []
    head = 0
    time = 0

    while head < len(q):
        name = q[head][0]
        cost = q[head][1]
        head += 1
        time += cost
        done.append((name, time))

    return done

jobs = [("A", 3), ("B", 2), ("C", 5)]
print(process_jobs(jobs))
# [('A', 3), ('B', 5), ('C', 10)]

main.rs

fn process_jobs(jobs: Vec<(&str, i32)>) -> Vec<(String, i32)> {
    let q = jobs;
    let mut done: Vec<(String, i32)> = Vec::new();
    let mut head: usize = 0;
    let mut time = 0;

    while head < q.len() {
        let name = q[head].0;
        let cost = q[head].1;
        head += 1;
        time += cost;
        done.push((name.to_string(), time));
    }
    done
}

fn main() {
    let jobs = vec![("A", 3), ("B", 2), ("C", 5)];
    println!("{:?}", process_jobs(jobs));
}

스택/큐 실전 확인 연산 순서 추적

큐는 도착 순서가 처리 순서를 결정하는 문제에 적합합니다.
예제처럼 누적 시간 정보를 함께 기록하면 디버깅과 성능 추정이 쉬워집니다.
처리 시간 정책(선점/비선점)이 바뀌면 우선순위 큐가 필요할 수 있습니다.

평균 시간복잡도: O(N)
최악 시간복잡도: O(N)
공간복잡도: O(N)

BFS 최소 거리

문제 의도: 큐 기반 BFS로 시작 정점에서 각 정점까지 최단 간선 수를 구합니다.
입력 예시: n=6, edges=[(0,1),(0,2),(1,3),(2,4)], start=0
출력 예시: [0,1,1,2,2,-1] dist[nxt] = dist[cur] + 1 한 줄이 한 단계 더 이동했다는 뜻입니다.

main.cpp

#include <iostream>
#include <utility>
#include <vector>
using namespace std;

vector<int> shortestSteps(int n, const vector<pair<int, int>>& edges, int start) {
    vector<vector<int>> graph(n);
    for (int i = 0; i < static_cast<int>(edges.size()); ++i) {
        int u = edges[i].first;
        int v = edges[i].second;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    vector<int> dist(n, -1);
    dist[start] = 0;
    vector<int> q;
    int head = 0;
    q.push_back(start);

    while (head < static_cast<int>(q.size())) {
        int cur = q[head];
        head += 1;
        for (int nxt : graph[cur]) {
            if (dist[nxt] != -1) continue;
            dist[nxt] = dist[cur] + 1;
            q.push_back(nxt);
        }
    }
    return dist;
}

int main() {
    vector<pair<int, int>> edges = {{0, 1}, {1, 2}, {0, 3}, {3, 4}, {4, 5}};
    vector<int> ans = shortestSteps(6, edges, 0);
    for (int x : ans) cout << x << " ";
    cout << "\n";
    return 0;
}

Main.java

import java.util.*;

public class Main {
    static int[] shortestSteps(int n, int[][] edges, int start) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
        for (int[] e : edges) {
            int u = e[0], v = e[1];
            graph.get(u).add(v);
            graph.get(v).add(u);
        }

        int[] dist = new int[n];
        Arrays.fill(dist, -1);
        dist[start] = 0;
        List<Integer> q = new ArrayList<>();
        int head = 0;
        q.add(start);

        while (head < q.size()) {
            int cur = q.get(head);
            head += 1;
            for (int nxt : graph.get(cur)) {
                if (dist[nxt] != -1) continue;
                dist[nxt] = dist[cur] + 1;
                q.add(nxt);
            }
        }
        return dist;
    }

    public static void main(String[] args) {
        int[][] edges = {{0,1},{1,2},{0,3},{3,4},{4,5}};
        System.out.println(Arrays.toString(shortestSteps(6, edges, 0)));
    }
}

main.py

def shortest_steps(n, edges, start):
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)

    dist = [-1] * n
    dist[start] = 0
    q = [start]
    head = 0

    while head < len(q):
        cur = q[head]
        head += 1
        for nxt in graph[cur]:
            if dist[nxt] != -1:
                continue
            dist[nxt] = dist[cur] + 1
            q.append(nxt)

    return dist

print(shortest_steps(6, [(0,1),(1,2),(0,3),(3,4),(4,5)], 0))
# [0, 1, 2, 1, 2, 3]

main.rs

fn shortest_steps(n: usize, edges: &[(usize, usize)], start: usize) -> Vec<i32> {
    let mut graph = vec![Vec::<usize>::new(); n];
    for &(u, v) in edges {
        graph[u].push(v);
        graph[v].push(u);
    }

    let mut dist = vec![-1i32; n];
    dist[start] = 0;
    let mut q: Vec<usize> = Vec::new();
    let mut head: usize = 0;
    q.push(start);

    while head < q.len() {
        let cur = q[head];
        head += 1;
        for &nxt in &graph[cur] {
            if dist[nxt] != -1 {
                continue;
            }
            dist[nxt] = dist[cur] + 1;
            q.push_back(nxt);
        }
    }
    dist
}

fn main() {
    let edges = vec![(0usize, 1usize), (1, 2), (0, 3), (3, 4), (4, 5)];
    println!("{:?}", shortest_steps(6, &edges, 0));
}