1. 문제
백준 1874번 스택 수열 - https://www.acmicpc.net/problem/1874
✅ 알고리즘 분류 - 자료 구조, 스택
🥈 난이도 - Silver 3
2. 풀이
문제에서도 말했듯이 스택은 제일 나중에 들어간 자료가 제일 먼저 나오는 LIFO(Last In First Out) 특성을 가지는 자료 구조입니다.
스택의 이러한 특성을 이용하면 이 문제를 쉽게 풀 수 있습니다.
n이 6이고 출력된 수열이 4,3,6,5,2,1인 예제로 설명드려보겠습니다.
문제의 조건에 따르면 idx=0 위치에 있는 4가 스택에서 pop되어 출력되려면 스택에 1,2,3,4가 순서대로 push된 후 pop되어야 합니다. (result = “++++-”)
첫번 째 수를 출력했으니 이제 다음 수인 3을 출력시켜봅시다.
다음 수인 3은 이미 스택에 있고 스택의 최상단에 있으므로 pop해주면 3도 출력시킬 수 있습니다. (result = “++++--”)
다음 수인 6은 스택에 없으므로 스택에 넣었던 최대값 4보다 큰 5부터 6까지 push하고 pop합니다. (result = “++++--++-”)
이 이후 5,2,1은 스택을 세번 pop하면 순서대로 출력시킬 수 있게됩니다.
(result = “++++--++----”)
이제 출력을 시키지 못하는 경우를 살펴보겠습니다.
idx = 2까지는 앞과 동일하게 진행됩니다.
이제 idx=3 위치에 있는 숫자 2를 출력 시켜야 하는데 pop을 시키면 숫자 5가 출력되게 됩니다.
이처럼 스택에서 pop한 값이 현재 idx위치에 있는 값과 다른 경우가 출력이 불가능한 경우입니다.
이제 이 과정을 간략히 정리해 보면 다음과 같습니다.
- 문제의 입력을 일차원 배열에 저장한다.
- 스택에 넣었던 최댓값+1 (최초에는 1) 부터 배열의 현재 인덱스의 값까지 스택에 push를 하고 그 때마다 결과에 “+”를 추가합니다.
- 스택에 pop을 하고 pop한 값이 현재 인덱스의 값이랑 동일한지 확인합니다.
- 동일한 경우에는 인덱스를 1증가시키고 결과에 “-”를 추가합니다. 그리고 이 과정을 인덱스가 n이 될 때까지 반복합니다.
- 만약 다른경우에는 진행하지 않고 “NO”를 출력하고 종료합니다.
3. 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static int n;
public static int[] arr;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
arr = new int[n];
for (int i=0; i<n; i++)
arr[i] = Integer.parseInt(br.readLine());
getResult();
}
public static void getResult() {
StringBuilder sb = new StringBuilder();
Stack<Integer> stack = new Stack<>();
int inc = 1;
int idx = 0;
while (idx < n) {
while (inc <= arr[idx]) {
stack.add(inc++);
sb.append("+").append("\n");
}
if (stack.pop() != arr[idx]) {
System.out.println("NO");
return;
}
sb.append("-").append("\n");
idx++;
}
System.out.println(sb);
}
}4. 결과
