기초 알고리즘 - 스택 수열(4)

문제를 이해하는 시간이 꽤 걸렸다.
1에서 n까지의 숫자를 순서없이 입력받고, 1부터 n까지를 오름차순으로 스택에 push 와 pop을 이용해서 입력받은 순서대로 수열을 만들어야한다.

43687521을 입력받으면,

push1 -> push2 -> push3 -> push4 -> pop4 -> pop3-> push5->push6 -> pop6-> push7 -> push8 -> pop8 -> pop7 -> pop5 -> pop2 -> pop1

이렇게 해당 입력된 순번에 도달할 때까지는 push, 그리고 숫자가 수열에 일치하면 pop을 실행한다.

사실 이해하고나면 원리자체는 간단하다.

• n을 입력받으면 n크기의 배열arr안에 수열을 입력받는다.
• 반복문을 통해서 1부터 차례로 push하다가 arr[0]에 맞닥뜨리면 pop하고, arr의 인덱스 값을 증가시켜준다.
• 반복문에서 push일때는 +를 StringBuilder에 입력받고, pop일 때는 -를 입력받는다.

끝이다. 이것을 코드로 구현해보도록 해야겠다.

상당히 간단하지 않았다 ㅋㅋ... 간단한데 생각이 꼬이고 꼬이면 어느순간 산으로 가있다. 결국엔 정답.

이 배열에 맞는 순서에 맞게 반복을 통해 i를 증가시키며 +를 입력받았다. 처음엔 1234를 push하고 4를 pop하고 1부터 다시push해서 start를 arr[j], 즉 마지막으로 push한 값으로 할당해줬다.

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

public class Hello_world {
 
	public static void main(String[] args) throws IOException {
		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];
		//n까지의 숫자를 순서대로 저장.
		for(int i=0; i<n; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		int start = 0;
		int j =0;
		while(n-->0) {
		if(arr[j] > start) {
		for(int i=start+1; i<=arr[j]; i++) {
			stack.push(i);
			sb.append('+').append('\n');
			
		}
		start = arr[j];
	} else if(stack.peek() != arr[j]) {
		System.out.print("NO");
		return;
	}
		stack.pop();
		sb.append('-').append('\n');
		j++;
}
		
		
		System.out.println(sb);
	}
}