백준 1874 <스택 수열>

1874번: 스택 수열 (acmicpc.net)

1874번: 스택 수열

input되는 숫자의 갯수와 그 숫자들로  순서대로 수열을 하나 만들고, 그 숫자 오름차순으로 스택에다가 push를 하며 중간중간 pop을 하며 이 수열을 만들 수 있는가? 를 묻는 문제이다.

 

문제가 약간 어렵게 느껴질수도 있는데,  예제 1을 보면, 8 > 4 3 6 8 7 5 2 1 순으로 수열이 나열되어있다. 하지만 오름차순으로 push를 해야하기에 1 2 3 4 를 push하고 4를 pop하고, 3을 pop하면 수열의 첫째 둘쨰항인 4 3 이 나온다.

이런식으로 6을 만들기 위해 5 6 을 push한후 6을 다시 pop해야한다. 그렇다면 pop되지 않고 push만 하여 남은 숫자들을 나중에 쌓였던 스택의 순서대로 pop하여 수열을 만들 수 있는가를 묻는것이다.

 

처음 나의 접근은 주어지는 수열 자체의 구조에 집중을 했다. 예를들어 수열이 오름차순이거나 내림차순이면 자명하게 스택으로 수열을 만들 수 있다. 예제 1와 예제 2같은 일반적인 수열의 경우는 마지막 인덱스와 그 전 인덱스의 대소관계로 접근해봤지만 이는 반례가 생길 수 있는 가능성이 너무 많고, 코드로 짜기 쉽지가 않다.

 

 두번째 접근은 일단 오름차순대로 push를 할 수 있는 것이니 위 접근 처럼 수열 자체에 집중을 하는것이 아닌, 주어지는 수열의 순서대로 스택에다가 push를 하는것이다. 

예제 1의 첫번째 항은 4이다. 여기서 1 2 3 4 push를 한다. 즉 여기서 push를 하는 조건은 다음 항 (예제 1에선 3) 보다 클 조건에서 push를 해야겠다. (4까지  push를 한 후, 4를 pop하는 상황에서 다음 항이 5 이면 push를 해야하지만, 3이나 2면 pop을해야한다.

 

 여기서 변수를 하나 설정하여 만약 첫째항까지의 push pop이 끝났다면, 첫째항을 변수로 담아, 이 첫째항보다 클때 push를 이어나간다. push를 한 후엔 변수를 다시 그 항의 정수로 초기화를 해야한다.

 

 

 

 만약 첫째항보다 작다면 push를 하지 않고 pop을 한번 더 해야하는데, 이때 조건문을 하나 걸어줘야한다. 

일단 pop을 한번 더 할때, 위의 예시로는 스택의 현상태는 

3

2

1

을 이루고 있을 것이다. 이때 다음항 즉 둘째항이 3이 아닌 다른 숫자라면 pop을 한다면 필연적으로 3이 나올텐데, input된 수열의 둘째항이 3이 아닌 다른 숫자라면 ( 아마 1,2 둘 중에 하나겠다)  같은 수열의 구조로 만들 수 없기에 프로그램을 강제 종료한다.

 

package 스택과큐;
import java.io.*;

import java.util.*;
public class _1874_스택수열 {
	
	

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		Stack<Integer> stack = new Stack<Integer>();
		int n = Integer.parseInt(br.readLine());
		int start =  0;
		while(n-- >0) {
			int target = Integer.parseInt(br.readLine());
			if(target>start) {
				for(int i=start+1; i<=target; i++) {
					stack.push(i);
					sb.append("+").append('\n');
					
				}
				start = target;
				
			}
			//반복문이 돌 동안, stack의 맨 위의값이 target 즉 수열의 다음 값과 다를경우, stack이라는 구조때문에 손 쓸 수 있는 방법이없다.
			else if(stack.peek() != target) {
				System.out.println("NO");
				return;
			}
			stack.pop();
			sb.append("-").append('\n');
		}
		System.out.println(sb);
		
		
	}

}

 

>> 문제에서 주어진 정보 그대로 코드를 짜면 되는 문제였다. 너무 복잡하게 수열을 일반화 하려해서 어렵게 풀었던것 같다.