[백준] 1874 스택 수열 - Data Structure / Java

• 문제 링크

1874번: 스택 수열

 

• 풀이 과정

입력받은 수열을 input 배열에 저장하고 Stack 을 활용하여 구현한다.

 

1 ~ n 까지 오름차 순으로 스택에 push() 할 종료 조건이 오름차 순의 수가 n에 도달 시 인 while 문을 생성,

스택에 값이 삽입될 때마다 StringBuilder에 '+' 를 줄 바꿈과 함께 더한다.

 

스택이 비어있지 않고, peek() 함수로 반환한 스택의 맨 상단의 값이 input 배열에 저장된 수열의 인덱스 값과 같을 시

while 문으로 조건에 만족하는 값을 연속해서 pop() 하며 '-' 를 StringBuilder 에 더한다.

 

끝으로 스택이 비어있다면 모든 수를 비교해 온전한 결과가 출력된 것이므로

그대로 StringBuilder 변수를 결과로써 출력하고,

아직 스택에 원소가 남아있다면 주어진 조건에 만족하지 못한 것이므로 "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 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();

		int n = Integer.parseInt(br.readLine());
		int[] input = new int[n];

		for (int i = 0; i < n; i++)
			input[i] = Integer.parseInt(br.readLine());

		Stack<Integer> stk = new Stack<>();

		int num = 1;
		int idx = 0;
		while (num <= n) {
			stk.push(num);
			sb.append("+\n");
			num++;

			while (!stk.empty() && stk.peek() == input[idx]) {
				stk.pop();
				sb.append("-\n");
				idx++;
			}
		}

		if (stk.empty())
			bw.write(sb + "");
		else
			bw.write("NO" + "");

		bw.flush();
	}

}