BOJ 1874번 스택 수열 문제 자바(java) 풀이
문제 정리
- 1부터 n까지의 수를 스택에 넣었다가 뽑으면서 주어진 수열을 만들어야 한다.
- 만들 수 있다면 push와 pop 연산 순서를 출력하고 만들 수 없다면 "NO"를 출력해라.
문제 풀이
처음에 문제 이해가 잘 안되서 헤맸었습니다.
예제 1번은 다음과 같이 동작합니다.
1. 1을 넣는다. (1)
2. 2를 넣는다. (1 2)
3. 3을 넣는다. (1 2 3)
4. 4를 넣는다. (1 2 3 4)
5. 수열의 첫번째 수 4가 stack의 맨 위의 수가 같으므로 pop한다. (1 2 3)
6. 다음 수 3이 stack의 맨 위의 수와 같으므로 pop한다. (1 2)
7. 5를 넣는다. (1 2 5)
8. 6을 넣는다. (1 2 5 6)
9. 세번쨰 수 6이 stakc의 맨 위의 수가 같으므로 pop한다 (1 2 5)
10. 7을 넣는다. (1 2 5 7)
11. 8을 넣는다. (1 2 5 7 8)
12. 수열의 네번째 수 8과 stack의 맨 위의 수가 같으므로 pop한다(1 2 5 7)
13. 이하 똑같이 반복하며 stack이 모두 비게 됩니다.
14. stack이 비게 되었으므로 수열 순서대로 만들 수 있습니다.
백준 스택 수열 자바 소스 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
class Main {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Stack<Integer> stack = new Stack<>();
StringBuilder sb = new StringBuilder();
int n = Integer.parseInt(br.readLine());
int i=1;
int cnt = 0;
int a = Integer.parseInt(br.readLine());
while(true) {
// stack이 비어있지 않다면
if(!stack.isEmpty()) {
// stack의 맨 위의 수와 다음 수열의 수가 같은지 확인
if(stack.peek() == a) {
// 같다면 pop
sb.append("-").append("\n");
stack.pop();
cnt++;
// 수열을 모두 생성한 경우
if(cnt == n)
break;
// 다음 수 입력받기
a = Integer.parseInt(br.readLine());
continue;
}
}
stack.add(i++);
sb.append("+").append("\n");
// i가 n+1이 넘으면 수열을 생성할 수 없는 경우
if(i > n+1)
break;
}
if(stack.size() == 0)
System.out.print(sb);
else
System.out.println("NO"); // stack에 남아 있다면 수열을 생성하지 못함
}
}