https://www.acmicpc.net/problem/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
문제에 설명이 조금 부족한 것 같아서 처음에 이해를 잘 못했습니다.
유투브에 검색해서 설명을 듣고 풀어보았습니다.
이 문제에 예제 1을 먼저 설명하겠습니다.
8개의 정수를 입력받았고 4라는 숫자가 첫 번째로 입력되었습니다.
그러면 스택에 1부터 4까지 push 해서 쌓아줍니다.
그 후 4를 pop하여 빼줍니다. 그러면 입력된 4라는 정수의 처리가 끝났고, 스택에는 1,2,3 이 남아있습니다.
다음 정수로 3이 입력되었습니다. 그러면 스택에서 바로 3을 pop 해줍니다.
그러면 스택에는 1,2 가 남아있습니다. 여기서 세 번째 정수로 6이 입력되었습니다.
그러면 스택에 1부터 6까지 쌓는 것이 아니고 최대치로 쌓았던 4 라는 숫자를 넘겨서 쌓아야됩니다. 즉, 5,6 을 쌓아
1,2,5,6 을 만들어주는 것입니다.
그 후 6을 pop하여 1,2,5 가 된 것입니다. 이렇게 반복하면 됩니다.
예제 2번으로 보면
첫 번째 1을 쌓아서 스택에 1 이 되었고 pop 하여 빼줍니다.
그 후 입력된 2를 push 이전 최대치가 1이었으므로 2만 push 후 pop
그 다음 5가 입력되었으므로 최대치가 2 이니 3부터 해서 3,4,5 푸시 후 pop 하면 3,4 가 남습니다.
여기서 3 이 들어왔습니다. 3,4 인 상태에서 스택은 4를 빼지 않고서는 3을 뺄 수 없습니다. 그래서 NO 가 출력됩니다.
전체 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Stack;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Stack<Integer> stack = new Stack<>();
int n = Integer.parseInt(br.readLine());
int max = 0;
ArrayList<String> result = new ArrayList<>();
for (int i=1; i<=n; i++){
int num = Integer.parseInt(br.readLine());
if (num > max) {
for (int j=max+1; j<=num; j++){
stack.push(j);
result.add("+");
}
max = num;
stack.pop();
result.add("-");
} else {
int pop_num = stack.pop();
if (pop_num > num){
result.clear();
result.add("NO");
break;
} else {
result.add("-");
}
}
}
result.stream().forEach(System.out::println);
}
}코드설명
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Stack<Integer> stack = new Stack<>();
int n = Integer.parseInt(br.readLine());
int max = 0;
ArrayList<String> result = new ArrayList<>();입력은 BufferedReader 로 받았으며, 스택을 생성해줍니다.
n개의 정수를 입력받기 위한 변수 n을 선언했습니다.
max 값을 얻기 위해 0으로 초기화했습니다.
결과값 "+", "-" 출력을 위해 ArrayList로 만들었습니다.
for (int i=1; i<=n; i++){
int num = Integer.parseInt(br.readLine());
if (num > max) {
for (int j=max+1; j<=num; j++){
stack.push(j);
result.add("+");
}
max = num;
stack.pop();
result.add("-");
} else {
int pop_num = stack.pop();
if (pop_num > num){
result.clear();
result.add("NO");
break;
} else {
result.add("-");
}
}
}예제1로 설명하겠습니다.
0이 아닌 1부터 입력된n까지 반복합니다.
현재 입력된 값을 num 변수로 입력받습니다.
현재 max 값과 num의 값을 비교하여 num이 크면 max+1 값으로 num 까지 스택에 push 해줍니다.
즉 4가 들어오면 max 초기 값이 0이므로 1부터 4까지 쌓은 것입니다.
결과 값 출력을 위해 리스트에 "+"를 추가합니다.
그 후 max를 num 값으로 바꿔주고 pop를 하여 처음 입력된 정수의 처리를 마칩니다.
pop를 했으니 리스트에 "-"를 추가합니다.
이 후 3이 들어왔으니 max값보다 작으므로 그대로 pop해줍니다. pop한 값을 현재 num이랑 비교하여 pop한 값이 num보다 크지 않은지 검사합니다. 크지 않다면 pop 했으니 리스트에 "-"를 추가해줍니다.
다음 정수로 6이 입력되었습니다. max 값보다 크므로 max+1 즉 5부터 6까지 5,6 을 추가하고 똑같이 6을 pop 해줍니다.
이렇게 반복하면 1예제가 끝납니다.
예제2 설명하겠습니다.
입력된 정수 1
push, pop
입력된 정수 2
push, pop
입력된 정수 5
3,4,5 push, pop 로 3,4 가 남습니다.
입력된 정수 3
if (pop_num > num){
result.clear();
result.add("NO");
break;
}스택에 남아있는 수는 3,4 여기서 3을 바로 뺄 수 없기 때문에 해당 if 문에 걸려 NO가 출력됩니다.
result.stream().forEach(System.out::println);마무리로 ArrayList를 출력하고 끝납니다.
문제 난이도는 실버3 으로 어려운 난이도는 아니지만 문제설명이 너무 부실합니다...