2025. 3. 11. 20:27ㆍ코딩테스트
오늘은 Stack 알고리즘에 대해 알아보자
우선 Stack 자료구조를 먼저 알아보자
스택은 LIFO(후입선출) 형식의 자료구조이다
말 그대로 나중에 들어온 자료가 먼저 나간다는 의미이다. 간단하게 설명 할 수 있지만 더 자세히 이해하기위해 스택을 구현하는 코딩테스트 문제로 알아보자
https://www.acmicpc.net/problem/10828
백준 10828 스택 문제이다. 두가지 풀이 방식이 존재하는데 하나는 Stack 자료구조를 이용하지 않고 배열을 이용해 구현하는 방법
두번째는 Stack 자료구조를 이용하는 방법이다.
스택에 대해 무지하거나 스택을 구현해본적이 없다면 첫번째 방법을 먼저 시도해보는게 좋을것이라 생각된다. 우선 첫번째 풀이다.
public class S_4_10828 {
public static int[] stack;
public static int size = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st;
int N = Integer.parseInt(br.readLine());
stack = new int[N];
while (N-- > 0) {
st = new StringTokenizer(br.readLine(), " ");
switch (st.nextToken()) {
case "push" :
push(Integer.parseInt(st.nextToken()));
break;
case "pop" :
sb.append(pop()).append('\n');
break;
case "size" :
sb.append(size()).append('\n');
break;
case "empty" :
sb.append(empty()).append('\n');
break;
case "top" :
sb.append(top()).append('\n');
break;
}
}
System.out.println(sb);
}
// 스택에 정수 X 를 추가하는 메서드 push
public static void push(int X) {
stack[size] = X;
size++;
}
// 스택의 가장 위에 존재하는 정수 X를 꺼내는 메서드 pop
public static int pop() {
if (size == 0) {
return -1;
} else {
int res = stack[size - 1];
stack[size - 1] = 0;
size--;
return res;
}
}
//스택의 크기를 출력하는 메서드 size
public static int size() {
return size;
}
//스택이 비어있는지 확인하는 메서드 empty
public static int empty() {
if (size == 0) {
return 1;
} else {
return 0;
}
}
//스택의 가장 위에 존재하는 정수를 확인하는 메서드 top() 꺼내는거 아님
public static int top() {
if (size == 0) {
return - 1;
} else {
return stack[size - 1];
}
}
}
편의를 위해 stack과, size를 static으로 빼놨다.
현재 스택에 있는 원소의 개수를 나타내고, 가장위에 존재하는 원소의 index를 알기 위한 변수 size가 필요하다.
두번째 풀이방법인 Stack 자료구조를 사용한 풀이다.
public class S_4_10828_V2 {
public static Stack<Integer> stack = new Stack<>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
for (int i = 0; i < n; i++) {
String command = br.readLine();
if (command.startsWith("push ")) {
String[] split = command.split(" ");
push(Integer.valueOf(split[1]));
} else if (command.equals("pop")) {
pop();
} else if (command.equals("size")) {
size();
} else if (command.equals("empty")) {
isEmpty();
} else if (command.equals("top")) {
top();
}
}
}
public static void push(int num) {
stack.push(num);
}
public static void pop() {
if (!stack.isEmpty()) {
System.out.println(stack.pop());
} else {
System.out.println("-1");
}
}
public static void size() {
System.out.println(stack.size());
}
public static void isEmpty() {
if (stack.isEmpty()) {
System.out.println(1);
} else {
System.out.println(0);
}
}
public static void top() {
if (!stack.isEmpty()) {
System.out.println(stack.peek());
} else {
System.out.println(-1);
}
}
}
stack을 구현해본적이 없다면 첫번째 풀이방법을 추천하지만 스택 자료구조에 대해 잘 알고 구현해본적도 있으면 실전 처럼 두번째 방식으로 푸는게 훨씬 빠를것이다. 위의 풀이와 다른점이 존재한다면 top 명령어에 대해서 stack.peek() 을 사용해서 가장 위에 존재하는 정수를 확인한다는 것이다. 나머지 명령어는 isEmpty(), size(), push(int X), pop() 모두 동일하다 또한 이 문제에서는 정수 X를 스택에 저장하는것이기에 Stack<Integer> 제네릭을 Integer 타입으로 제한했다.
여기서 왜? Stack<int>를 쓰지 않았나 자바 제네릭은 기본타입을 직접 사용할 수 없고 참조타입만 사용할 수 있기 때문이다. 따라서 래퍼 클래스인 Integer을 사용했다.
두 풀이 방법 모두 시간 복잡도가 O(N) 이지만 직접 구현하는 것보다는 Stack 클래스를 이용하는게 훨씬 간결하고 빠르게 작성 가능하니
스택을 구현해본적이 있다면 두번째 풀이를 사용하자
기본적인 스택을 알아봤으니 이제 스택 알고리즘의 문제 유형에 대해 알아보자
1. 괄호 문제
https://www.acmicpc.net/problem/4949
괄호문제의 대표적인 예시이다.
열린괄호와 닫힌는 괄호의 균형을 맞추는 문제이다.
스택을 통해 "(", "{", "[" 같은 열린괄호들을 push 하고 peek 이나 pop 메서드를 이용해 현재 열린 괄호와 균형이 맞는지 유효성 검사를 하는 유형이다.
문자열의 길이(N)만큼 순회 하기 때문에 시간복잡도는 O(N)이다.
public class S_4_4949 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
while (true) {
String s = br.readLine();
Stack<Character> stack = new Stack<>();
if (s.equals(".")) {
break;
}
boolean isBalanced = true;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(' || c == '[') {
stack.push(c);
} else if (c == ')' || c == ']') {
if (stack.isEmpty() || (c == ')' && stack.peek() != '(') || (c == ']' && stack.peek() != '[')) {
isBalanced = false;
break;
} else {
stack.pop();
}
}
}
if (isBalanced && stack.isEmpty()) {
System.out.println("yes");
} else {
System.out.println("no");
}
}
}
}
2. 쇠막대기 문제
https://www.acmicpc.net/problem/10799
괄호문제와 유사하지만 살짝 응용이 필요한 유형이다.
() 이렇게 괄호가 붙어있을 경우만 레이저고 레이저가 나오면 현재 존재하는 막대기 개수만큼 조각이 생긴다.
왜냐하면 현재 존재하는 막대기 개수 == 스택의 크기 따라서 count += stack.size()
그렇지 않은경우 닫힌괄호가 나오지만 레이저가 아닌경우 즉 막대기의 끝부분이라는 것이다 이 경우는 하나의 조각이 추가 되는것이기 때문에 stack.pop() 이후 count++
이 경우도 문자열의 길이(N) 만큼 순회하기 때문에 시간복잡도는 O(N)이다.
public class S_2_10799_V2 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String s = br.readLine();
Stack<Character> stack = new Stack<>();
int count = 0;
stack.push(s.charAt(0));
for (int i = 1; i < s.length(); i++) {
if (s.charAt(i) == '(') {
stack.push(s.charAt(i));
} else {
if (s.charAt(i - 1) == '(') {
stack.pop();
count += stack.size();
} else {
stack.pop();
count++;
}
}
}
System.out.println(count);
}
}
3. 프렛 문제
https://www.acmicpc.net/problem/2841
맨 처음에는 문제가 잘 이해가 안갔지만 이해하고 나면 그렇게 어려운 문제는 아니다.
현재 누르고 있는 프렛보다 더 높은 프렛을 누르면 push, 낮은 프렛을 연주하려면 pop을 하면된다
주의할점은 각 줄마다 스택이 필요하다는 것이다. 따라서 Stack<Integer>[] 배열을 만들어냈다.
모든 입력을 한번씩 순회 하기 때문에 시간복잡도는 O(N)이다.
public class S_1_2841 {
public static int N;
public static int P;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
P = Integer.parseInt(st.nextToken());
Stack<Integer>[] stacks = new Stack[7];
for (int i = 1; i <= 6; i++) {
stacks[i] = new Stack<>();
}
int totalMoves = 0;
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
int note = Integer.parseInt(st.nextToken());
int fret = Integer.parseInt(st.nextToken());
while (!stacks[note].isEmpty() && stacks[note].peek() > fret) {
stacks[note].pop();
totalMoves++;
}
if (stacks[note].isEmpty() || stacks[note].peek() != fret) {
stacks[note].push(fret);
totalMoves++;
}
}
System.out.println(totalMoves);
}
}
'코딩테스트' 카테고리의 다른 글
| 코테 연습 - 이분탐색 (0) | 2025.04.29 |
|---|---|
| 코테연습 - 정렬 (1) | 2025.04.22 |
| 코테연습 - 백트래킹 (0) | 2025.04.01 |
| 코테연습 - 재귀 (0) | 2025.03.25 |
| 코테연습 - bfs/dfs (0) | 2025.03.17 |