🧩 BE
home

1874_스택 수열

담당자
완료 여부
Solved
요약
날짜
2025/04/14
태그
자료구조
난이도
S2
출처
백준
2가지 조건이 중요하다.
1.
push는 반드시 오름차순
2.
때문에 순차 입력을 위해 start 변수를 초기화해주며 pop을 실행해야함
입력기준 4 3 6 8 7 5 2 1 기준으로 4를 입력하면 1 2 3 4를 모두 순서대로 stack에 push해야하는 것.
start = 0 value = input() 만약 value > start -> i+1(1부터니까) ~~ <= value까지 push -> start 초기화!! 만약 peek != value면 -> 더이상 탐색할 필요 없음. NO 반환하고 종료 pop
Plain Text
복사
따라서 위의 논리를 n번 반복하면 된다.
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.Deque; // 스택에 push하는 순서는 반드시 오름차순 // 목표 수열을 스택으로 만들 수 있는가 public class Main { static int n; static int[] nums; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); n = Integer.parseInt(br.readLine()); // 목표 수열 입력 nums = new int[n]; for (int i = 0; i < n; i++) { nums[i] = Integer.parseInt(br.readLine()); } Deque<Integer> stack = new ArrayDeque<>(); StringBuilder sb = new StringBuilder(); int start = 0; int idx = 0; while (idx < n) { int value = nums[idx]; // start + 1부터 value까지 push if (start < value) { for (int i = start + 1; i <= value; i++) { stack.push(i); sb.append("+\n"); } // 오름차순 유지해야하니까 변수 초기화 start = value; } // top 원소가 입력값과 다르면 else if (stack.peek() != value) { System.out.println("NO"); return; } stack.pop(); sb.append("-\n"); // 인덱스 증가시켜주기 idx++; } System.out.println(sb); } }
Java
복사