[백준]1874번 스택수열

문제

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

1874번: 스택 수열

---

코드(JAVA)

import java.io.*;
import java.util.*;

public class Main{
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		Stack<Integer> stack = new Stack<>();
		int n = Integer.parseInt(br.readLine());
		int[] arr = new int[n];
		for(int i =0 ;i < n ; i++) arr[i] =  Integer.parseInt(br.readLine());
		int cnt = 1;
		int i;
		for(i =0 ; i < n ; i++) {
			if(stack.isEmpty()) {
				if(cnt>arr[i]) break;
				stack.push(cnt++);
				sb.append("+\n");
			}
			if(arr[i] > stack.peek()) {
				if(cnt > arr[i]) break;
				while(stack.peek() != arr[i]) {
					stack.push(cnt++);
					sb.append("+\n");
				}
			}
			else if(arr[i] < stack.peek()) {
				while(stack.peek() != arr[i]) {
					stack.pop();
					sb.append("-\n");
				}
			}
			if(arr[i] == stack.peek()) {
				stack.pop();
				sb.append("-\n");
			}
		}
		if(i != n || !stack.isEmpty()) System.out.println("NO");
		else System.out.print(sb.toString());
	}
}

---

설명

입력: BufferedReader

출력: StringBuilder

 

기본적으로, 

현재 비교하고 있는 배열 값(arr[i])과 현재 stack에 맨 위에 값을 비교.

If(arr[i] > stack.peek())이라면,

아직 스택에 해당 값(arr[i])가 안들어가 있는 경우이므로 stack.peek() == arr[i]까지 스택에 cnt를 push

If(arr[i] < stack.peek())이라면,

스택안에 해당 값이 들어있는 경우이므로, stack.pop값이 arr[i]일때까지 pop

 

이때, 주의 할 점.

push할 때, 현재 스택에 들어갈 값(cnt)보다 비교 할 값(arr[i])가 더 크다면

스택에는 계속 arr[i]보다 큰값만 쌓이게 되고, 결국 무한루프를 돌게 됨.

 

이 부분에 대한 분기문을 잘 활용해야 메모리초과, 시간초과가 나지 않음 (ノへ￣、)

---

반례(내 코드 기준!)

1
1
+
-

3
1
2
3
+
-
+
-
+
-

4
4
2
3
1
NO