자바 백준 1874번 문제 - 스택 수열

문제 출처 : https://www.acmicpc.net/problem/1874

1874번: 스택 수열

 

문제 : 

 

풀이 :

1부터 n까지의 수를 스택에 넣었다가 뽑으면, 즉 stack.push()되고 stack.pop()되면 수열로 들어간다는 것이다.

1부터 n까지의 수를 push()와 pop() 해서 입력된 수열로 만드는 것이니

우선 입력된 수열을 int[] arr로 저장하고 n와 arr 배열을 solution함수로 넘겨준다.

solution함수에선 1부터 n까지의 수를 입력된 수열대로 만들기 위해 스택을 사용한다.

 

n이 8이고 입력된 수가 4 3 6 8 7 5 2 1 의 경우라고 가정하자. 이 배열은 solution 함수에서 int[] arr로 전달된다.

1부터 n까지의 수를 이용해 이 배열의 수열대로 만들어야 한다.

앞서 말했다시피 stack.push()되고 stack.pop()되면 수열로 들어가게 된다.

 

p1은 시작점 인덱스와 1부터 순서대로 담기는 수(p1+1) 의미, 입력받았던(만들고자 하는) 수열의 인덱스 p2

n이 8이고 입력된 수가 4 3 6 8 7 5 2 1 의 경우

처음엔 p1 = 0, p2 = 0 ( 그럼 여기서 arr[p2]는 4이다. )

 

if (p1 < arr[p2])

스택에 시작점 인덱스인 p1부터 arr[p2]까지 stack.push()한다.

스택 : {1, 2, 3, 4}  /  수열 : { }

p1 = 4 (이후 5부터 시작한다는 것이다.) , p2 = 0 (이후 stack.pop() 할 때 p2++해준다. 당장은 오르지 않는다.)

// 위 p1값이 변한 것은 스택에 넣고 이후 다시 오름차순으로 n까지 수를 봐야 하니 p1 = arr[p2] 해준 것이다.

 

else if (stack.peek() != arr[p2])

p1 < arr[p2] 가 아닌데 스택의 맨 위 값이 arr[p2]에 없는 경우 입력받은 수열을 만들 수 없다는 뜻이므로

바로 "NO"를 리턴하고 끝낸다.

 

그 외엔 stack.pop()하고 p2++ 해준다.

스택 : {1, 2, 3, 4}  /  수열 : { }  ->

스택 : {1, 2, 3}  /  수열 : {4}  ->  

스택 : {1, 2}  /  수열 : {4, 3}

현재 p1 = 4, p2 = 2 이므로

1부터 n까지의 수는 5부터 시작되고, 비교하고자 하는 입력받은 수열은 arr[2], 즉 6이 된다.

그러면 이제 다시 p1 < arr[p2]에서 처리되고.. 이런 과정이 n번 반복되게 된다.

 

소스코드 :

import java.util.*;
class Main {
	public StringBuilder solution(int n, int[] arr) {
		Stack<Integer> stack = new Stack<>();
		StringBuilder sb = new StringBuilder();
		// p1은 시작점 인덱스와 1부터 순서대로 담기는 수(p1+1) 의미, 입력받았던(만들고자 하는) 수열의 인덱스 p2
		int p1 = 0, p2 = 0, cnt = 0;
		while (cnt < n) {
			if (p1 < arr[p2]) {
				for(int i=p1+1; i<=arr[p2]; i++) {
					stack.push(i);
					sb.append('+').append('\n');
				}
				p1 = arr[p2];
			}
			else if (stack.peek() != arr[p2]) {
				sb.setLength(0);
				sb.append("NO");
				return sb;
			}
			stack.pop();
			p2++;
			cnt++;
			sb.append('-').append('\n');
		}
		return sb;
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt(); // 8
		int[] arr = new int[n];
		for(int i=0; i<n; i++) arr[i] = sc.nextInt();
		System.out.println(T.solution(n, arr));
	}
}