[알고리즘] 백준 1874번 : 스택 수열

알고리즘 문제 출처 : https://www.acmicpc.net/problem/1874

1874번: 스택 수열

 

내가 작성한 코드

처음에는 문제가 이해가 되지 않았다. 다시 읽고 이해를 했는데 그러니까 스택에 1,2,3,...,n까지 차례대로 넣을 건데 주어진 숫자가 [4, 3, 6, 8, 7, 5, 2, 1]와 같이 주어졌다면 4를 꺼내기 위해서 1~4까지 스택에 push하고 4가 가장 위에 있을 때 pop하고 그 다음 3을 pop하고 5, 6까지 스택에 push하고 6이 가장 위에 있을 때 pop하고 이런 식이라는 말이다.

계속 메모리 초과가 떠서 난감했던 문제. 원래는 String형 answer 변수를 따로 두고 스택에 넣거나 뺄 때마다 answer += "+\n"나 answer += "-\n"와 같이 계속해서 문자를 누적하여 더해갔는데 이게 메모리를 상당히 잡아먹는 모양이다. 스택에서 끄집어내야 할 수가 스택 최상단의 수보다 작은 경우는 NO를 출력해야 하므로 구분이 필요했는데 대신 FIFO인 큐를 사용해서 +와 -를 차곡차곡 쌓고 하나씩 빼서 출력했다. answer 변수를 없애자마자 문제 통과.

-> 계속 메모리 초과가 나왔던 이유를 알았다. StringBuilder를 사용해서 문자를 더해가면 메모리 초과를 극복할 수 있다. 예전에 이와 관련해서 공부를 했었는데 막상 문제를 풀 때는 떠올리지 못하고 이제 와서 생각하니 조금 황당하다. 다음 번에는 꼭 써먹어야지( 관련 포스팅 : https://hayden-archive.tistory.com/148#stringbuilder ) 

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

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		Stack<Integer> stack = new Stack<>();
		Queue<String> queue = new LinkedList<String>();
		int index = 1;
		boolean flag = true;
		for(int i=0; i<n; i++) {
			int num = Integer.parseInt(br.readLine());
			while(index<=num) {
				stack.push(index++);
				queue.add("+");
			}
			if(stack.lastElement()==num) {
				stack.pop();
				queue.add("-");
			}else if(stack.lastElement()>num) {
				flag = false;
				break;
			}
		}
		if(flag == false) {
			bw.write("NO");
		}else {
			while(!queue.isEmpty()) {
				bw.write(queue.poll()+"\n");
			}
		}
		bw.flush();
		bw.close();
	}
}