새소식

알고리즘 문제풀이/BOJ

[BOJ] 백준 1874번 스택 수열 자바(java) 풀이

  • -

BOJ 1874번 스택 수열 문제 자바(java) 풀이

문제 정리

  1. 1부터 n까지의 수를 스택에 넣었다가 뽑으면서 주어진 수열을 만들어야 한다.
  2. 만들 수 있다면 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에 남아 있다면 수열을 생성하지 못함 } }
Contents

포스팅 주소를 복사했습니다

이 글이 도움이 되었다면 공감 부탁드립니다.