[백준] 1874번 : 스택 수열 (JAVA)

드디어 스택 마지막 문제인 1874번 : 스택 수열을 풀었다.

 

 

스택에 대해 아직 이해하지 못했다면 다음의 블로그에서 확인하면 된다.

https://lucy1215.tistory.com/17

[자료구조] 스택 (Stack)

 

바로 앞 문제인 4949번 : 균형잡힌 세상 에 대한 내용은 바로 앞의 블로그에서 확인하면 된다.

https://lucy1215.tistory.com/21

[백준] 4949번 : 균형잡힌 세상 (JAVA)

 

---

<문제>

<문제 해석>

스택을 이용하여 1부터 n까지에 수에 대해

주어진 수열을 나타낼 수 있는지 판별해라.

 

- 수열을 나타낼 수 있으면 push 연산은 + , pop 연산은 - 을 출력

- 수열을 나타낼 수 없으면 NO 출력

 

 

 

<문제 해결>

이 문제 또한 스택을 잘 이해하고 있다면 어렵지 않은 문제이다.

 

예제 2번으로 자세하게 설명을 하겠다.

1부터 5까지 주어질 때, 스택을 이용하여  수열 [1, 2, 5, 3, 4]을 만들 수 있는지 판별하는 것이다.

이해하기 쉽게 그림을 그리면서 설명하겠다.

 

스택에 push하는 숫자는 오름차순이여야 하기때문에 

1, 2, 3, 4, 5 순서대로 push를 해야한다.

 

 

1. 1을 push한다.

 

 

2. 수열의 첫 숫자가 1이기 때문에 1을 pop() 한다.  수열 : [1]

 

 

3. 2를 push한다.

 

 

 

4. 수열의 다음 숫자가 2이기 때문에 2를 pop()한다. 수열 : [ 1, 2 ]

 

 

 

5. 수열 5를 출력하기 위해 3, 4, 5 를 순서대로 push한다.

 

 

 

6. 5를 pop() 한다. 수열 : [1, 2, 5]

 

 

 

7. 다음 수열인 3을 꺼내야하는데 맨 위의 숫자가 4여서 무조건 4를 꺼내고 3을 꺼내야한다.

    따라서 해당 수열을 만들 수 없다.

    결과 : NO

 

 

 

위의 설명을 보면 해당 문제의 알고리즘을 찾을 수 있다.

 

<알고리즘>

1. 해당 수열의 숫자가 나올때까지 숫자들을 오름차순으로 push한 뒤,

 

2. 해당 수열의 숫자가 나오면 stack에 pop()을 실행하면 된다.

 

3. 만약 스택의 맨 위 숫자가 해당 수열의 숫자가 아니면  해당 수열은 만들 수 없는 것이다.

 

 

 

 

<코드>

import java.io.IOException;
import java.util.Scanner;
import java.util.Stack;

public class Main {	
	public static void main(String[] args) throws IOException {
		
		Stack<Integer> stack = new Stack<>();
		
		Scanner sc = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();
		
		int n = sc.nextInt();
		int start = 0;
		while(n-- > 0) {
			int value = sc.nextInt();
			 
			if(value > start) {
				for(int i=start+1;i<=value;i++) {
					stack.push(i);
					sb.append('+').append('\n');
				}
				
				start = value;
			}
			
			if(stack.peek() == value) {
				stack.pop();
				sb.append('-').append('\n');
			}
			
			else if(stack.peek() != value) {
				System.out.println("NO");
				return;
			}
		}
		System.out.println(sb);
	}
}

 

 

 

---

https://www.acmicpc.net/problem/1874

1874번: 스택 수열