반응형
백준_1874
1874번: 스택 수열
1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다.
www.acmicpc.net
스택(Stack)
삽입과 삭제 연산이 후입선출(LIFO : Last-in First-out)으로 이루어진 자료구조이다. 후입선출은 산입과 삭제가 한 쪽에서만 이루어진다.
스택 용어
- top : 삽입과 삭제가 일어나는 위치
- push : top 위치에 새로운 데이터를 삽입하는 연산
- pop : top 위치에 현재 있는 데이터를 삭제하고 확인하는 연산
- peek : top 위치에 현재 있는 데이터를 단순 확인하는 연산
스택은 깊이 우선 탐색(DFS : Depth First Search), 백트래킹 종류의 코딩 테스트에 효과적이다.
후입선출은 개념 자체가 재귀 함수 알고리즘 원리와 일맥상통한다.
코드
import java.util.Scanner;
import java.util.Stack;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr = new int[n];
for(int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
Stack<Integer> stack = new Stack<>();
StringBuilder sb = new StringBuilder();
int num = 1;
for(int i = 0; i < n; i++) {
int su = arr[i];
if(su >= num) {
while(su >= num) {
stack.push(num++);
sb.append("+\n");
}
stack.pop();
sb.append("-\n");
}
else {
int top = stack.pop();
if(top > su) {
System.out.println("NO");
return;
}
else {
sb.append("-\n");
}
}
}
System.out.println(sb.toString());
}
}스택이란 자료구조를 잘 이해하고, 사용할 줄 안다면 나름 쉽게 풀리는 문제이다..!
제출 결과
반응형