스택 / 큐 / 해시맵

학습 목표: 스택/큐 활용 문제 패턴 · 해시맵을 이용한 효율적 탐색 · 우선순위 큐(힙) 기초 · 괄호 매칭, 최빈값 등 대표 유형

1️⃣ 스택 (Stack)

개념

후입선출(LIFO, Last In First Out) 구조 = 마지막에 넣은 게 먼저 나오는 구조.

🥞 비유: 팬케이크 쌓기! 맨 위에 올린 걸 맨 먼저 먹는거 처럼 나중에 넣은 걸 먼저 꺼내는 구조.

push(1) → [1]
push(2) → [1, 2]
push(3) → [1, 2, 3]
pop()   → 3 반환, [1, 2]
pop()   → 2 반환, [1]

파이썬에서 스택 구현

stack = []

stack.append(1)   # push
stack.append(2)
stack.append(3)

print(stack.pop())  # 3 - 마지막 넣은 게 먼저 나옴
print(stack.pop())  # 2
print(stack[-1])    # 1 - pop 없이 맨 위 확인 (peek)

🔑 대표 패턴 1 - 괄호 매칭

코딩테스트 스택 문제의 국룰 유형임.

def is_valid_parentheses(s):
    stack = []
    mapping = {')': '(', '}': '{', ']': '['}

    for char in s:
        if char in mapping:                         # 닫는 괄호
            top = stack.pop() if stack else '#'
            if mapping[char] != top:
                return False
        else:                                       # 여는 괄호
            stack.append(char)

    return not stack  # 스택이 비어있으면 True

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

📍 풀이 흐름:

s = "{[]}"
'{' → push  → stack: ['{']
'[' → push  → stack: ['{', '[']
']' → pop   → '[' 꺼냄, mapping[']'] == '[' ✅
'}' → pop   → '{' 꺼냄, mapping['}'] == '{' ✅
스택 비어있음 → True

🔑 대표 패턴 2 - 단조 스택 (Monotonic Stack)

"다음으로 큰 수 찾기" 같은 유형에 쓰임

# 문제: 각 원소에 대해 오른쪽에서 처음 만나는 더 큰 수 찾기
def next_greater_element(arr):
    n = len(arr)
    result = [-1] * n
    stack = []  # 인덱스 저장

    for i in range(n):
        # 스택 top보다 현재 값이 크면 → 그게 정답
        while stack and arr[stack[-1]] < arr[i]:
            idx = stack.pop()
            result[idx] = arr[i]
        stack.append(i)

    return result

arr = [2, 1, 2, 4, 3]
print(next_greater_element(arr))  # [4, 2, 4, -1, -1]

2️⃣ 큐 (Queue)

개념

선입선출(FIFO, First In First Out) 구조/ 먼저 넣은 게 먼저 나오는 구조.

🎟️ 비유: 줄 서기! 먼저 온 사람이 먼저 들어가는 거(스택이랑 반대)

enqueue(1) → [1]
enqueue(2) → [1, 2]
enqueue(3) → [1, 2, 3]
dequeue()  → 1 반환, [2, 3]
dequeue()  → 2 반환, [3]

파이썬에서 큐 구현

from collections import deque

queue = deque()

queue.append(1)    # enqueue
queue.append(2)
queue.append(3)

print(queue.popleft())  # 1 - 먼저 넣은 게 먼저 나옴
print(queue.popleft())  # 2

⚠️ 왜 list 대신 deque?list.pop(0)은 O(n)이지만 deque.popleft()는 **O(1)**이야.
큐는 무조건 deque 써!

🔑 대표 패턴 - BFS (너비 우선 탐색)

큐의 가장 대표적인 활용이야. 그래프/트리 탐색에서 핵심!

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    result = []

    while queue:
        node = queue.popleft()
        result.append(node)

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

    return result

graph = {
    1: [2, 3],
    2: [4, 5],
    3: [6],
    4: [], 5: [], 6: []
}
print(bfs(graph, 1))  # [1, 2, 3, 4, 5, 6]

3️⃣ 해시맵 (HashMap / Dictionary)

개념

키(Key) - 값(Value) 쌍으로 데이터를 저장하는 구조. 키로 값을 찾는 데 O(1) 밖에 안 걸려서 빠름!

📖 비유: 책의 목차! "3장" 이라는 키를 찾으면 바로 페이지(값)로 이동함.

# 파이썬 dict = 해시맵
hash_map = {}

hash_map["apple"] = 3     # 삽입: O(1)
hash_map["banana"] = 5

print(hash_map["apple"])  # 조회: O(1) → 3
print("banana" in hash_map)  # 존재 확인: O(1) → True
del hash_map["banana"]    # 삭제: O(1)

🔑 대표 패턴 1 - 최빈값 찾기

from collections import Counter

def most_frequent(arr):
    count = Counter(arr)          # 각 원소의 빈도 계산
    return count.most_common(1)[0][0]  # 가장 많이 나온 원소

arr = [1, 3, 2, 3, 4, 3, 2, 1, 3]
print(most_frequent(arr))  # 3

# Counter 없이 직접 구현
def most_frequent_manual(arr):
    freq = {}
    for x in arr:
        freq[x] = freq.get(x, 0) + 1

    return max(freq, key=freq.get)

🔑 대표 패턴 2 - Two Sum (해시맵 버전)

1주차에서 투 포인터로 풀었던 문제를 해시맵으로 O(n)에 풀기.

def two_sum(nums, target):
    seen = {}  # {값: 인덱스}

    for i, num in enumerate(nums):
        complement = target - num

        if complement in seen:
            return [seen[complement], i]

        seen[num] = i

    return []

nums = [2, 7, 11, 15]
print(two_sum(nums, 9))   # [0, 1] → 2 + 7 = 9
print(two_sum(nums, 18))  # [1, 2] → 7 + 11 = 18

📍 핵심 아이디어:target - 현재값 = 필요한 값 → 이미 본 값들 중에 있냐?
해시맵에 저장해두면 O(1)에 확인 가능!

🔑 대표 패턴 3 - 해시맵을 이용한 효율적 탐색

# 문제: 배열에서 중복된 원소가 있는지 확인
def has_duplicate(nums):
    seen = set()
    for num in nums:
        if num in seen:
            return True
        seen.add(num)
    return False

print(has_duplicate([1, 2, 3, 4]))   # False
print(has_duplicate([1, 2, 3, 1]))   # True

# 문제: 두 배열의 교집합 찾기
def intersection(nums1, nums2):
    set1 = set(nums1)
    return list(set(x for x in nums2 if x in set1))

print(intersection([1,2,2,1], [2,2]))  # [2]

4️⃣ 우선순위 큐 / 힙 (Priority Queue / Heap)

개념

일반 큐와 다르게 우선순위가 높은 원소가 먼저 나오는 구조야. 파이썬은 기본적으로 최소 힙(Min Heap) 을 제공해. (가장 작은 값이 먼저 나옴)

🏥 비유: 응급실 대기! 먼저 온 사람이 아니라 더 위급한 환자가 먼저 진료받는거.

import heapq

heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 4)
heapq.heappush(heap, 1)
heapq.heappush(heap, 5)

print(heapq.heappop(heap))  # 1 (최솟값)
print(heapq.heappop(heap))  # 1
print(heapq.heappop(heap))  # 3

최대 힙 만들기 (파이썬 꿀팁)

파이썬 heapq는 최소 힙만 지원해서, **값에 음수(-)**를 붙이는 트릭을 쓴다.

import heapq

heap = []
nums = [3, 1, 4, 1, 5, 9, 2, 6]

for num in nums:
    heapq.heappush(heap, -num)   # 음수로 저장

print(-heapq.heappop(heap))  # 9 (원래 최댓값)
print(-heapq.heappop(heap))  # 6

🔑 대표 패턴 - K번째 큰 수 찾기

import heapq

def find_kth_largest(nums, k):
    # 최소 힙으로 크기 k 유지
    heap = []

    for num in nums:
        heapq.heappush(heap, num)
        if len(heap) > k:
            heapq.heappop(heap)  # 가장 작은 거 제거

    return heap[0]  # 힙의 최솟값 = k번째 큰 수

nums = [3, 2, 1, 5, 6, 4]
print(find_kth_largest(nums, 2))  # 5

# 시간복잡도: O(n log k) - 전체 정렬 O(n log n)보다 효율적!

5️⃣ 유형별 5문제 풀이 & 풀이 비교

👉🏻 유형 1 - 스택: 올바른 괄호

입력: s = "()[]{}"
출력: True

입력: s = "([)]"
출력: False

접근법: 여는 괄호는 push, 닫는 괄호는 pop해서 짝이 맞는지 확인.

👉 유형 2 - 큐: 프린터 우선순위 (카카오 스타일)

입력: priorities = [2, 1, 3, 2], location = 2
출력: 3  (location=2인 문서가 3번째로 출력)

from collections import deque

def printer_priority(priorities, location):
    queue = deque(enumerate(priorities))  # (인덱스, 우선순위)
    count = 0

    while queue:
        idx, priority = queue.popleft()
        # 현재보다 우선순위 높은 게 남아있으면 뒤로 보냄
        if any(priority < p for _, p in queue):
            queue.append((idx, priority))
        else:
            count += 1
            if idx == location:
                return count

👉 유형 3 - 해시맵: 완주하지 못한 선수

참가자 명단에서 완주자 명단을 빼면 남는 1명 찾기

from collections import Counter

def find_incomplete(participant, completion):
    count = Counter(participant)
    for p in completion:
        count[p] -= 1
    # 값이 1 이상인 사람이 완주 못한 선수
    return [p for p, c in count.items() if c > 0][0]

👉 유형 4 - 힙: K개의 가장 빈번한 원소

import heapq
from collections import Counter

def top_k_frequent(nums, k):
    count = Counter(nums)
    # (-빈도, 값) 형태로 최대 힙처럼 사용
    return [val for val, _ in Counter(nums).most_common(k)]

nums = [1, 1, 1, 2, 2, 3]
print(top_k_frequent(nums, 2))  # [1, 2]

👉 유형 5 - 해시맵 + 슬라이딩 윈도우: 최소 윈도우 부분 문자열

from collections import Counter

def min_window(s, t):
    need = Counter(t)
    missing = len(t)
    start, end = 0, 0
    best = ""

    for right, c in enumerate(s, 1):
        if need[c] > 0:
            missing -= 1
        need[c] -= 1

        if missing == 0:  # t의 모든 문자 포함
            while need[s[start]] < 0:
                need[s[start]] += 1
                start += 1

            window = s[start:right]
            if not best or len(window) < len(best):
                best = window

            need[s[start]] += 1
            missing += 1
            start += 1

    return best

print(min_window("ADOBECODEBANC", "ABC"))  # "BANC"

📌 2주차 핵심 요약

1. 스택 (LIFO)
   → 파이썬: list.append() / list.pop()
   → 대표 유형: 괄호 매칭, 단조 스택

2. 큐 (FIFO)
   → 파이썬: deque.append() / deque.popleft()  (list.pop(0) 쓰지 말 것!)
   → 대표 유형: BFS, 프린터 우선순위

3. 해시맵
   → 파이썬: dict, set, Counter
   → O(1) 삽입/탐색/삭제
   → 대표 유형: Two Sum, 빈도 카운팅, 중복 확인

4. 우선순위 큐 (힙)
   → 파이썬: heapq (기본 최소 힙, 최대 힙은 음수 트릭)
   → 대표 유형: K번째 큰 수, 최빈 원소

🔥 더 나은 접근법 토론

문제 유형	브루트포스	최적화	개선 포인트
Two Sum	이중 for문 O(n²)	해시맵 O(n)	이미 본 값 저장
K번째 큰 수	전체 정렬 O(n log n)	힙 O(n log k)	k 크기 힙 유지
중복 확인	이중 for문 O(n²)	set O(n)	해시 셋 활용
괄호 매칭	재귀 O(n²)	스택 O(n)	LIFO 특성 활용

🔗 연습 문제 추천 (LeetCode)

Valid Parentheses (#20) - 스택 기본
Min Stack (#155) - 스택 응용
Implement Queue using Stacks (#232) - 스택 + 큐 변환
Two Sum (#1) - 해시맵 기본
Top K Frequent Elements (#347) - 힙 + 해시맵
Find Median from Data Stream (#295) - 힙 심화

🗓️ 다음 주 예고: 트리 & 그래프 (DFS / BFS 심화)