오늘의 핵심 주제는 네 가지 자료구조입니다.
스택 (Stack)
큐 (Queue)
덱 (Deque)
우선순위 큐(Priority Queue, 힙 구조)
저번 글까지는 배열, 문자열, 완전 탐색 위주로 직접 하나하나 돌려보는 연습을 했다면,
이번 글부터는 자바 자료구조를 이용해서 문제를 더 깔끔하게 푸는 패턴을 익혀보려고 합니다.
각 자료구조의 개념과 자바 코드 사용법, 코딩테스트에서 자주 나오는 활용 패턴까지 정리해보겠습니다.
Ⅰ. 목표
자바의 스텍, 큐, 덱, 우선순위 큐를 자유롭게 사용할 수 있고,
어떤 문제에 어떤 자료구조를 써야 할지 감이 오는 상태 만들기
구체적인 목표는 다음과 같습니다.
- 스택으로 괄호 검사, 되돌리기(Undo) 등 LIFO 패턴 구현
- 큐로 순서대로 처리하는 FIFO 문제 구현
- 덱으로 양쪽에서 넣고 빼는 시뮬레이션 문제 해결
- 우선순위 큐로 항상 가장 작은/큰 값을 빠르게 꺼내는 패턴 익히기
Ⅱ. 스택 (Stack)
- 개념
스택은 Last In, First Out (LIFO) 구조입니다.
- 예시
- 브라우저 뒤로 가기
- 되돌리기(Undo)
- 괄호 짝 맞추기
- 특징
- 가장 나중에 들어간 데이터가 먼저 나온다.
- 메서드
- push(item): 스택 맨 위에 값 추가
- pop(): 스택 맨 위의 값을 꺼내면서 제거
- peak(): 스택 맨 위의 값을 조회(제거 X)
- isEmpty(): 스택이 비어 있는지 확인
- size(): 현재 스택에 들어있는 원소 개수
- 자바에서 사용법
자바에서는 Stack 클래스를 그대로 사용하거나, Deque를 스택처럼 사용할 수 있습니다.
가장 단순한 Stack 사용 예시는 다음과 같습니다.
import java.util.Stack;
Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);
int top = stack.pop(); // 3. 스택에서 삭제됨
int peek = stack.peek(); // 2. 삭제는 안 됨
boolean empty = stack.isEmpty();
실전 코딩테스트에서는 Stack 또는 ArrayDeque 둘 다 사용 가능하지만,
성능과 권장사항 측면에서는 ArrayDeque를 스택처럼 쓰는 방식도 많이 쓰입니다.
import java.util.ArrayDeque;
import java.util.Deque;
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1); // 스택 상단에 삽입
int x = stack.pop(); // x == 1, 스택 상단에서 제거
- 대표 문제: 괄호 검사
가장 전형적인 스택 문제는 괄호의 짝이 올바른지 확인하는 문제입니다.
접근 방식은 다음과 같습니다.
- 문자열을 왼쪽부터 한 글자씩 본다.
- 여는 괄호 '('가 나오면 스택에 push
- 닫는 괄호 ')'가 나오면
- 스택이 비어 있으면 잘못된 문자열
- 스택에서 pop해서 짝을 맞추기
- 문자열을 끝까지 처리했을 때
- 스택이 비어 있으면 올바른 괄호 문자열
- 비어 있지 않으면 잘못된 문자열
코드는 다음과 같이 작성할 수 있습니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String s = br.readLine();
for (int i=0; i<s.length(); i++) {
char c = s.charAt(i);
if (c == '(') {
stack.push(c);
} else if (c == ')') {
if (stack.isEmpty()) {
valid = false;
break;
}
stack.pop();
}
}
if (!stack.isEmpty()) {
valid = false;
}
System.out.println(valid ? "YES" : "NO");
}
}
이런 패턴은 중괄호, 대괄호, 태그 검사 등으로 확장해서 자주 등장합니다.
Ⅲ. 큐(Queue)
- 개념
큐는 First In, First Out (FIFO) 구조입니다.
- 예시
- 줄 서기
- 프린터 작업 대기열
- BFS(너비 우선 탐색)에서 사용
- 특징
- 먼저 들어온 데이터가 먼저 처리된다.
- 메서드
- offer(item): 큐의 맨 뒤에 원소 추가. 실패 시 false
- add(item) : 큐의 맨 뒤에 원소 추가. 실패 시 예외
- poll(): 큐의 맨 앞 원소를 꺼내면서 제거. 비어 있으면 null
- remove(): 큐의 맨 앞 원소 제거 후 반환. 비어 있으면 예외
- peek(): 맨 앞 원소를 보기만 함(제거 X). 비어 있으면 null
- element() : 맨 앞 원소를 보기만 함(제거 X). 비어 있으면 예외
- isEmpty(): 큐가 비어있는지 확인
- size(): 큐의 원소 개수
- 자바에서 큐 사용법
일반적으로 Queue 인터페이스와 LinkedList 또는 ArrayDeque를 함께 사용합니다.
import java.util.LinkedList;
import java.util.Queue;
Queue<Integer> queue = new LinkedList<>();
queue.offer(1); // 삽입
queue.offer(2);
queue.offer(3);
int x = queue.poll(); // 1 (가장 먼저 들어온 값)
int y = queue.peek();
boolean empty = queue.isEmpty();
- 대표 문제 패턴: 카드 게임 시뮬레이션
1부터 N까지 번호가 적힌 카드가 순서대로 있을 때
- 맨 위 카드를 버리고
- 그 다음 맨 위 카드를 맨 아래로 보내는 행동을 반복했을 때
- 마지막에 남는 카드 번호를 구하기
이 문제는 큐를 이용해 자연스럽게 해결할 수 있습니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
Queue<Integer> q = new LinkedList<>();
for (int i=1; i<=n; i++) {
q.offer(i);
}
while (q.size() > 1) {
q.poll(); // 맨 위 카드 버리기
q.offer(q.poll()); // 그 다음 카드를 맨 뒤로 보내기
}
System.out.println(q.poll());
}
}
이런 식의 순서대로 작업 처리 시뮬레이션은 큐로 구현하면 코드가 매우 깔끔해집니다.
Ⅳ. 덱 (Deque)
- 개념
덱(Deque, Double-Ended Queue)는 양쪽 끝에서 삽입과 삭제가 모두 가능한 큐입니다.
- 앞/뒤 양쪽에서 push, pop이 가능
- 예시
- 슬라이딩 윈도우
- 회전하는 큐
- 양쪽에서 요소를 넣고 빼는 시뮬레이션
- 삽입/삭제 메서드
- addFirst(item): 덱의 앞쪽에 원소 추가. 실패 시 예외
- addLast(item): 덱의 뒤쪽에 원소 추가. 실패 시 예외
- offerFirst(item): 덱의 앞쪽에 원소 추가. 실패 시 false
- offerLast(item): 덱의 뒤쪽에 원소 추가. 실패 시 false
- removeFirst(): 앞쪽 원소 제거 후 반환. 비어있으면 예외
- removeLast(): 뒤쪽 원소 제거 후 반환. 비어있으면 예외
- pollFirst(): 앞쪽 원소 제거 후 반환. 비어있으면 null
- pollLast(): 뒤쪽 원소 제거 후 반환. 비어있으면 null
- getFirst(): 앞쪽 원소 조회. 비어 있으면 예외
- getLast(): 뒤쪽 원소 조회. 비어 있으면 예외
- peekFirst(): 앞쪽 원소 조회. 비어 있으면 null
- peekLast(): 뒤쪽 원소 조회. 비어 있으면 null
- ArrayDeque를 스택처럼 사용할 때 메서드
- push(item): 스택처럼 상단에 추가 (실제로는 addFirst)
- pop(): 스택 상단에서 꺼내면서 제거 (removeFirst와 유사)
- peek(): 스택 상단 원소 조회 (peekFirst와 유사)
- 자바에서 덱 사용법
자바에서는 ArrayDeque를 가장 많이 사용합니다.
import java.util.ArrayDeque;
import java.util.Deque;
Deque<Integer> deque = new ArrayDeque<>();
// 앞쪽에 삽입/삭제
deque.addFirst(1);
deque.addFirst(2);
int x = deque.removeFirst();
// 뒤쪽에 삽입/삭제
deque.addLast(3);
deque.addLast(4);
int y = deque.removeLast();
// 확인만
int front = deque.peekFirst();
int back = deque.peekLast();
- 대표 패턴: 회전하는 큐
예시로, 덱을 이용하여 양쪽으로 회전하는 큐 문제를 해결할 수 있습니다.
- 특정 값을 뽑기 위해
- 왼쪽으로 한 칸 회전 (앞의 요소를 뒤로)
- 오른쪽으로 한 칸 회전 (뒤의 요소를 앞으로)
- 두 동작 중 더 적은 회전 횟수를 선택하는 문제에서
- 덱을 이용하면 앞뒤를 자유롭게 움직일 수 있어 구현이 쉽습니다.
덱을 양쪽에서 삽입, 삭제를 동시에 지원하는 큐로 이해하고,
기본 메서드(addFirst, addLast, removeFirst, removeLast)를 직접 써보는 정도까지 연습하면 충분합니다.
Ⅴ. 우선순위 큐 (Priority Queue)
- 개념
우선순위 큐(Priority Queue)는 값의 크기(또는 우선순위)에 따라 먼저 나오는 요소가 정해지는 자료구조입니다.
- 기본 PriorityQueue는 최소 힙(min-heap) → 가장 작은 값이 먼저 나옴
- 응용
- 가장 작은/큰 값을 자주 꺼내야 하는 문제
- 힙 정렬, K번째 수, 합치기 비용 최소화 등
- 메서드
- offer(item)
- add(item)
- poll()
- remove()
- peek()
- element()
- isEmpty()
- size()
- clear(): 모든 원소 제거
- 자바에서 PriorityQueue 기본 사용법
최소 힙 (기본)
import java.util.PriorityQueue;
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(3);
pq.offer(1);
pq.offer(5);
int x = pq.poll(); // 1 (가장 작은 값부터)
int x = pq.poll(); // 3
최대 힙
import java.util.Collections;
import java.util.PriorityQueue;
PriorityQueue<Integer> maxPq = new PriorityQueue<>(Collections.reverseOrder());
maxPq.offer(3);
maxPq.offer(1);
maxPq.offer(5);
int x = maxPq.poll(); // 5 (가장 큰 값부터 나옴)
또는 람다식으로도 구할 수 있습니다.
PriorityQueue<Integer> maxPq = new PriorityQueue<>((a, b) -> b - a);
- 대표 문제 패턴: 최소 값부터 처리하기
여러 개의 숫자를 합치는 비용이 두 수의 합 만큼 들고,
계속 반복해서 하나가 될 때까지 합칠 때
전체 비용을 최소화 하는 문제
이런 경우, 항상 가장 작은 두 수부터 먼저 합치는 것이 최적 전략입니다.
PriorityQueue를 사용하면 매번 가장 작은 두 수를 쉽게 꺼낼 수 있습니다.
PriorityQueue<Integer> pq = new PriorityQueue<>():
// 값들 추가
for (int i=0; i<n; i++) {
pq.offer(Integer.parseInt(br.readLine()));
}
int cost = 0;
while (pq.size() > 1) {
int a = pq.poll();
int b = pq.poll();
int sum = a + b;
cost += sum;
pq.offer(sum);
}
System.out.println(cost);
이런 가장 작은 것부터 두 개씩 꺼내서 처리하는 유형은 우선순위 큐의 전형적인 사용 예입니다.
Ⅵ. 어떤 문제에 어떤 자료구조를 써야 할까?
- 스택 (Stack)
- 되돌리기, 괄호 검사, 뒤집기, 뒤로 가기
- 큐 (Queue)
- 순서대로 처리, 대기열, 회전 없이 한 방향으로만 흐르는 시뮬레이션, BFS
- 덱 (Deque)
- 양방향 회전, 앞뒤 양쪽에서 삽입/삭제가 필요한 시뮬레이션
- 우선순위 큐 (PriorityQueue)
- 항상 현재 가장 작은/큰 값을 꺼내야 하는 문제, 그리디와 함께 자주 등장
문제를 읽으면서
입력받은 순서대로 처리해야 하나?
최근 것부터 거꾸로 꺼내야 하나?
앞뒤 양쪽에서 넣고 빼야 하나?
항상 최소/최댓값을 꺼내야 하나?
를 스스로 물어보고, 그에 따라 자료구조를 선택하는 습관을 들이면 좋습니다.
Ⅶ. 체크리스트
- 자바에서 Stack, Queue, Deque, PriorityQueue를 직접 선언하고 기본 메서드를 쓸 수 있다.
- 스택으로 괄호 검사(올바른 괄호 문자열)를 구현할 수 있다.
- 큐를 사용해서 카드 게임처럼 앞에서 빼고 뒤로 보내는 시뮬레이션 문제를 풀 수 있다.
- 덱을 사용해서 양끝에서 삽입, 삭제가 필요한 간단한 문제를 구현할 수 있다.
- PriorityQueue로 최소 힙/최대 힙을 만들 수 있고, 각각 어떤 상황에서 사용하는지 설명할 수 있다.
- 문제를 읽고 어떤 자료구조가 어울리는지 파악할 수 있다.
다음 글에서는 정렬과 이분 탐색, 누적합을 이용해 시간 복잡도를 줄이는 패턴에 들어갈 예정입니다.
- 정렬 + 그리디
- 정렬 + 이분 탐색
- 구간 합을 빠르게 구하는 누적합
'Algorithm > 정리' 카테고리의 다른 글
| [코딩테스트] 정렬, 이진 탐색, 누적합 프로그래머스 문제 모음 (0) | 2025.12.10 |
|---|---|
| [코딩테스트] 정렬, 이진 탐색, 누적합으로 시간 복잡도 줄이기 (0) | 2025.12.10 |
| [코딩테스트] 배열, 문자열과 완전 탐색(Brute Force) (0) | 2025.12.09 |
| [코딩테스트] 빠른 입출력과 구현(시뮬레이션) 기본 패턴 (1) | 2025.12.09 |