TIL

가볍게 문제풀이로 스택 관련 문제를 하나 풀었다.
단계별 풀어보기 스택 문제 다 풀었다.

백준 1874번: 스택 수열

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

문제가 이해가 안가서 애먹었다.
입력값
8
4
3
6
8
7
5
2
1
가 있으면
8은 스택에 들어갈 수의 최대 갯수고
그다음은 만들어질 수열의 순서다

1. 스택에 4까지 넣는다. (++++) 그리고 4를 뺀다. (-)
2. 3을 뺀다. (-)
3. 스택에 5와 6을 넣는다. (++) 그리고 6을 뺀다.(-)
4. 스택에 7과 8을 넣는다. (++) 그리고 8을 뺀다.(-)
5. 스택에 7,5,2,1을 순서대로 뺀다. (----)

그러면 값이
++++--++-++----- 가된다.

근데 입력값
5
1
2
5
3
4
는 왜 안되느냐?
1. 스택에 5까지 넣는다. (+++++) 5를 뺀다. (-)
2. 1까지 뺀다. (-----)
3. 2를 빼려면 2를 다시 넣어야 한다. 근데 이미 넣었다..
이 수열은 가능하지 않음.

이미 넣었으면 다시 넣지 말아야 하기 때문에 count를 전역변수로 둔다.
그리고 count의 값이 새로 받을 정수만큼 될때까지 수를 스택에 넣는다.
스택의 peek가 타겟의 값과 같지 않으면 NO를 출력한다.

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

public class Main{
	static int temp=1;
	static int T;
	static int n;
	static StringBuilder sb;
	public static void main(String[] args) throws IOException {
		Stack<Integer> stack= new Stack<Integer>();
		
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw= new BufferedWriter(new OutputStreamWriter(System.out));
		
		sb= new StringBuilder();
		
		T= Integer.parseInt(br.readLine());

		for(int i=0;i<T;i++) {
			n= Integer.parseInt(br.readLine());
			
			for( ;temp<=n;temp++) {
				stack.push(temp);
				sb.append("+"+"\n");
			}
			
			if(stack.peek()==n) {
				stack.pop();
				sb.append("-"+"\n");
			}else {
				sb.setLength(0); 
				sb.append("NO");
				break;
			}
		}
		
		bw.write(sb.toString());
		bw.flush();
		bw.close();
		br.close();
	}
}

이 문제를 풀면서 메모리 초과가 났는데, 이유는 값을 String에 +연산으로 넣었기 때문이다.
StringBuilder의 append 연산을 사용하니 메모리 초과가 뜨지 않았다.
스택 개념보다 이 부분을 배운게 더 큰 의미가 있는듯.