[JAVA] BOJ(백준) - 스택 수열 - 1874

문제내용

스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다.

1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라.

입력

첫 줄에 n (1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄부터 n개의 줄에는 수열을 이루는 1이상 n이하의 정수가 하나씩 순서대로 주어진다. 물론 같은 정수가 두 번 나오는 일은 없다.

출력

입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력한다. push연산은 +로, pop 연산은 -로 표현하도록 한다. 불가능한 경우 NO를 출력한다.

 

---

문제 접근 방법

1~n까지 숫자를 차례대로 이용해서 문제에서 입력값으로 주어진 수열을 만들면서 push와 pop을 할때마다 + , - 로 표현해주면 되는 문제이다.

문제를 푸는 풀이방법은 간단하다.

1. 입력받은 값을 배열 arr에 넣어준다.
2. 스택에 1부터 오름차순으로 수를 넣으면서 arr배열의 idx번째 수와 비교한다.
3. 현재 탐색중인 값이 스택의 top값과 같다면 pop하고 StringBuileder에 ' - ' 를 추가한다.
4. 3번이 아니라면(값이 다르면) 스택에 그다음 넣을 숫자를 push후 StringBuileder에 '+'를 추가한다.
   1. 만약 이때 스택에 넣을값이 최대치(n)이라면 끝까지 다돌았음에도 수열이 안만들어진것으로 판단.
      함수종료 후 "NO"를 출력
5. 1~4번을 반복한다.
   이때 스택에 넣을값이 최대치(n)이면서 스택이 비어있다면 수열이 만들어진것이므로 종료.
   그게아니고 스택만 비어있을경우 4번 실행.

위의 과정을 반복하면된다.

 

자세한건 풀이를 보자

 

---

풀이

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

public class Main {
	static StringBuilder answer = new StringBuilder();
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[] arr = new int[n];
		
		for(int i=0; i<n; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		
		stackOper(arr,n);//스택 연산을 통해 +, - 를 answer에 삽입해줌.
		
		//answer의 마지막 2글자가 NO일때 NO출력후 함수 끝.
		if(answer.substring(answer.length()-2, answer.length()).equals("NO")) {
			System.out.println("NO");
			System.exit(0);
		}
		
		//answer출력
		System.out.println(answer.toString());
	}
	
	public static void stackOper(int[] arr, int n) {
		Stack<Integer> st = new Stack<Integer>();
		int stValue = 0; //스택에 넣을 값(오름차순)
		int idx = 0; //arr의 인덱스
		
		while(true) {
			//n까지 모든값이 돌았을때 종료조건
			if(stValue==n && st.isEmpty()) {
				break;
			}else if(st.isEmpty()) {//스택 비었을땐 바로 추가
				stValue++;
				st.add(stValue);
				answer.append("+").append("\n");
				continue;
			}
			
			int value = st.peek();//top값
			if(value!=arr[idx]) {//top과 현재 탐색중인 값이 다를때 값추가
				//이때 만약 스택에 넣을 값이 최대치라면
				//더이상 수열을 만들수 없다고 판단하고 함수 종료.
				if(stValue == n) {
					answer.append("NO");
					return;
				}
				stValue++;
				st.add(stValue);
				answer.append("+").append("\n");
			}else {//top과 현재 탐색중인 값이 같을때 값반환
				//탐색하는 값이 마지막값이 아니면 인덱스는 증가시켜줌
				if(idx != arr.length-1) idx++;
				st.pop();
				answer.append("-").append("\n");
			}
		}
	}
}

---

마치며

스택을 이용한 알고리즘은 짝을 맞추는 방식이 많은듯하다.