[자료구조] 백준 - 스택 수열

https://www.acmicpc.net/problem/1874

1874번: 스택 수열

 

-문제해설

스택에 1부터 n까지 오름차순으로 숫자를 집어넣으면서 push와 pop을 반복하여 입력받은 값들과 똑같이 만들면 되는 문제이다.

 

자바코드에서

첫 번째 풀이는 먼저 다 입력을 받고 하나하나 비교해나가는 풀이이고

두 번째 풀이는 다른 사람풀이를 참고하여 하나씩 입력받을 때마다 스택을 push, pop하는 코드이다.

 

첫 번째 풀이를 기준으로 설명하면

만약 입력값이 arr = [ 4 3 6 8 7 5 2 1 ] 이라고 하면

i라는 변수를 1부터 n까지 증가시키면서 arr의 값들과 비교한다.

이때 arr의 인덱스값인 idx는 0 부터 시작한다.

 

조건이 스택이 비워져있지 않거나 i가 n보다 작거나 같은 while문 안에서

i라는 변수와 arr[ idx ] 비교해서 i <= arr[idx] 이면 스택에 i를 집어넣는다.

처음 arr[0] = 4이므로 스택에는 i = 1, 2, 3, 4까지 들어간다.

 

그리고 i <= arr[idx]  인 5 <= arr[0] 이 성립이 안되므로 스택에서 가장 최근값을 pop시켜서 ans배열에 저장해준다.

그리고 ans[0]과 arr[0]하고 비교하여 같으면 계속 while반복문을 수행하고 다르면 NO를 StringBuffer에 저장하고 반복문을 빠져나온다.

 

이렇게 반복하다가 i가 9가 되었는데 스택이 비워져있지 않으면 스택이 비워질 때까지 계속 pop하여 ans배열에 저장한다. 그리고 ans배열과 arr배열과 비교를 해서 다르면 NO 같으면 스택을 계속 비운다.

 

 

 

-자바

package dataStructure;

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

public class BJ1874 {

	public static void main(String[] args) throws NumberFormatException, 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() );
		
		StringBuffer sb = new StringBuffer();
		Stack<Integer> s = new Stack<Integer>();
		
		int[] ans = new int[n];
		int idx = 0;
		int i = 1;
		int j = 0;
		while( !s.isEmpty() || i <= n ) {
			if( i > n ) {
				ans[j] = s.pop();
				sb.append( "-\n" );
				if( ans[j] != arr[j] ) {
					sb = new StringBuffer();
					sb.append( "NO\n" );
					break;
				}
				j++;
				
			} else if( i <= arr[idx] ) {
				sb.append( "+\n" );
				s.add( i++ );
			} else {
				ans[j] = s.pop();
				sb.append( "-\n" );
				idx++;
				
				if( ans[j] != arr[j] ) {
					sb = new StringBuffer();
					sb.append( "NO\n" );
					break;
				}
				j++;
			}
		}
		
		System.out.println( sb );
	}
}

-자바( 다른 사람 풀이 참고 )

package dataStructure;

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

public class BJ1874_1 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt( br.readLine() );
		
		StringBuffer sb = new StringBuffer();
		Stack<Integer> s = new Stack<Integer>();
		
		int start = 0;
		while( n --> 0 ) {
			int val = Integer.parseInt( br.readLine() );
			
			if( val > start ) {
				for( int i=start+1; i<=val; i++ ) {
					s.push( i );
					sb.append( "+\n" );
				}
				start = val;
			} else if( s.peek() != val ) {
				System.out.println( "NO" );
				return;
			}
			
			s.pop();
			sb.append( "-\n" );
			
		}
		System.out.println( sb );
	}
}

 

 

-파이썬

import sys
from collections import deque
l = sys.stdin.readline
n = int( l() )

res = "" 
s = deque()

s.append( 1 )
s.append( 2 )

start = 0
for _ in range( n ):
    val = int( l() )
    if start < val:
        for i in range( start+1, val+1 ):
            s.append( i )
            res += "+\n"
        start = val
    elif s[ len(s)-1 ] != val:
        print( "NO" )
        sys.exit()
    s.pop()
    res += "-\n"
print( res )