문제 : 스택수열

링크 : BOJ_1874_스택수열

접근 방식

1~n까지 증가해가면서 스택을 쌓다가, 수열에 해당하는 수를 만나면 수열에 해당하는 수가 더이상 나타나지 않을 때까지 반복해서 꺼낸다.

예를 들어 주어진 n값이 8이고, 수열이 4 3 6 8 7 5 2 1 이라고 하면.

1. 스택에 1,2,3,4 까지 push한다.
2. 스택의 top = 4, 수열의 첫 번째 값도 4, 두 값이 같기 때문에 pop한다. 수열의 카운트는 1 증가시켜 3을 가리킨다.
3. 스택의 top = 3, 수열의 두 번째 값은 3, 두 값이 같기 때문에 pop한다. 수열의 카운트는 1 증가시켜 6을 가리킨다.
4. 스택의 top = 2, 수열의 세 번째 값은 6, 두 값이 다르기 때문에 반복을 종료한다.
5. 스택에 5, 6 까지 push한다. . . .

이러한 방식으로 1부터 시작해서 n에 도달할 때까지 반복해서 돌려주면 된다.

풀이 방법

1. Stack 클래스를 사용해서 Integer 스택을 생성한다. 변수 N에 수열 개수를 읽어와 저장한다.
2. 수열은 값을 읽어와서 따로 배열에 저장해둔다.
3. StringBuilder 객체를 생성한다.
4. 1~N까지 반복문을 돌려 stack에 push하고 StringBuilder에 +를 append한다.
5. 중첩 반복문으로, 스택이 비어있거나 수열의 값과 스택의 최상위 값이 일치하면 stack를 pop하고, StringBuilder에 -를 append한다. 수열은 카운트를 1 증가시켜 다음 번호로 넘어간다.
6. 더이상 수열의 값과 스택의 최상위 값이 일치하지 않으면 내부 반복문을 빠져나간다.
7. 반복문이 모두 종료된 후 스택이 비어있다면 수열대로 정렬이 성공한 것이므로 지금까지 append시킨 StringBuilder를 출력한다.
8. 스택에 남아있는 값이 있다면 NO를 출력한다.

   소스 코드

   ~~~java

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Stack;

public class BOJ_1874_스택수열 {

public static void main(String[] args) throws NumberFormatException, IOException {
	BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

	int N = Integer.parseInt(in.readLine());
	Stack<Integer> stack = new Stack<>();
	int[] arr = new int[N];
	for (int i = 0; i < N; i++) {
		arr[i] = Integer.parseInt(in.readLine());
	}
	int cnt = 0;
	StringBuilder sb = new StringBuilder();

	for (int i = 1; i <= N; i++) {
		stack.push(i);
		sb.append("+\n");
		while (true) {
			if (!stack.empty() && arr[cnt] == stack.peek()) {
				sb.append("-\n");
				stack.pop();
				cnt++;
			} else {
				break;
			}
		}
	}
	if (stack.empty()) {
		System.out.println(sb);
	} else {
		System.out.println("NO");
	}

} }

~~~