push
와 pop
을 통해 임의의 수열을 만들 수 있는지 판단하며, 해당 수열을 오름차순을 지켜야 한다.예제를 살펴보면 수열의 첫번째 입력값이 '4'이므로 정수를 스택에 push
한다.
int start = 0; // 정수에 넣기 시작하는 값
int value = Integer.parseInt(br.readLine());
if(value > start) {
for(int i = start + 1; i <= value; i++){
stack.push(i);
}
start = value; // 이전에 어디까지 입력 받았는지 알기 위해 start를 value 값으로 초기화한다.
}
스택의 맨 위 원소가 첫번재 수열인 4라면 pop
하고, 같지 않다면 수열을 만족하지 못하므로 NO
를 출력한다.
else if(stack.peek() != value){
System.out.println("NO");
return;
} else if(stack.peek() == value) {
// value 값까지 push하면 pop을 한다.
stack.pop();
}
package Algorithm.P1874;
import java.io.*;
import java.util.*;
public class P1874 {
static int n;
static Stack<Integer> stack = new Stack();
static int start = 0;
public static void main(String[] args) throws IOException {
System.setIn(new FileInputStream("src/Algorithm/P1874/input.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
StringBuilder sb = new StringBuilder();
n = Integer.parseInt(st.nextToken());
while (n != 0) {
int value = Integer. parseInt(br.readLine());
if (value > start) {
for (int i = start + 1; i <= value; i++) {
stack.push(i);
sb.append('+').append('\n');
}
start = value;
}
else if (stack.peek() != value) {
System.out.println("NO");
return;
} else if (stack.peek() == value) {
stack.pop();
sb.append('-').append('\n');
}
n--;
}
System.out.println(sb);
}
}
Reference