[JAVA] 백준 1874번 스택 수열 : LIFO

1874번: 스택 수열

 

1. 문제 추상화

 

1부터 n까지 수로 이루어진 수열 A가 주어진다. 오름차순으로 스택에 push하여 수열A를 구현할 수 있는지 판별하시오.

구현이 불가능하면 NO를 출력하고 구현이 가능하면 어떤 과정을 통해 구현되는지 출력하시오. (push : '+' 출력, pop '-'출력' )

 

2. 알고리즘

 

조건은 두 가지이다. 

 

1. 스택을 사용하라.

2. 오름차순으로 push해라.

 

스택은 LIFO 특징을 가진다. 그리고 오름차순이니 작은 수가 First, 큰 수가 Last로 push해야한다.

그리고 큰 수부터 pop 해야한다. 고로 수열의 영역을 구분하면 아래와 같다.

 

4 3  /  6  /  8 7 5 2 1 ( 1874번 예시 수열 )

 

6은 4보다 크지만 4가 6보다 먼저 pop되었다. 이 말은 6이 push 되기 전에 4와 3이 pop되었다는 의미이다. 

 

이 원리를 이용하여 수열을 구현해보자.

 

1. PUSH

 

수열의 첫 수가 4이므로 4보다 작은 정수를 스택에 PUSH한다.

 

2. POP 

 

이제 POP할 차례다. 수열과 스택의 TOP을 하나씩 비교하여 POP한다.

 

 

수열의 0번째 인덱스 : 4

스택의 TOP : 4 => POP

 

수열의 1번째 인덱스 : 3

스택의 TOP : 3 => POP

 

수열의 2번째 인덱스 : 6 => 중단

 

 

6은 4보다 크므로 중단된다. 그리고 이같은 PUSH & POP을 반복한다. 스택에는 이미 1부터 4까지 들어갔었다. 그러므로 6보다 작고 4보다 큰 정수를 PUSH해야한다. 그러므로 pivot 변수를 만들어준다. 

 

첫 pivot은 0이다. 그러므로 4보다 작고 0보다 큰 수들을 push했다. 

다음 pivot은 4이다. 그러므로 6보다 작고 4보다 큰 수들을 push한다. 

이같은 과정을 반복하면 된다.

 

그리고 만약 수열의 값과 스택의 TOP가 값이 다르다면 이는 구현될 수 없는 수열이다. 스택은 오름차순으로 PUSH되기에 서로 다른 값이 나올 수 없다. 

 

수열의 1번째 인덱스 : 3

스택의 TOP : 4 => X ( 'NO' 출력 )

 

 

3. 코드 

 

import java.util.Scanner;
import java.util.Stack;

public class Main {
	public static Scanner sc = new Scanner(System.in);
	public static StringBuilder sb = new StringBuilder();
	public static Stack<Integer> stack = new Stack<Integer>();

	public static int[] arr; // 수열

	public static void main(String[] args) {
		makeArr(); // 수열 저장
		mainProcess();
		printResult();
	}
	
	public static void makeArr() {
		int size = sc.nextInt();
		arr = new int[size];
		
		for(int i = 0; i < size; i++) {
			arr[i] = sc.nextInt();
		}
	}
	
	public static void mainProcess() {
		int pivot = 0; // pivot
		int nextIndex = 0;
		
		for(int i=0; i<arr.length; i = nextIndex) {
			pushProcess(pivot,arr[i]); // PUSH
			nextIndex = popProcess(i); // POP
			if(!isValid()) break; // 수열 유효성검사
			pivot = arr[i]; // pivot 교체하기
		}
	}
	
	public static void pushProcess(int start, int end) {
			for(int j= start+1; j <= end; j++) {
				stack.push(j);
				sb.append("+").append("\n");
			}
	}
	
	public static int popProcess(int startIndex) {
		int nextIndex = startIndex;
		
		while( nextIndex < arr.length && arr[nextIndex] <= arr[startIndex] ) {
			if( stack.peek() == arr[nextIndex]) {
				stack.pop();
				sb.append("-").append("\n");
				nextIndex++;
			}else {
				sb = null;
				break;
			}
		}
		return nextIndex;
	}
	
	public static boolean isValid() {
		if(sb == null) {
			sb = new StringBuilder();
			sb.append("NO");
			return false;
		}
		else return true;
	}
	
	public static void printResult() {
		System.out.println(sb.toString());
	}

}