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
복사