011. 스택으로 오름차순 수열 만들기(백준1874번)

문제

문제 분석하기

문제에서 알 수 있는 정보들

• 시간제한 2초 = 약 2억번의 연산 안에 해결해야한다.
• 스택에 push하는 순서는 반드시 오름차순을 지켜야한다.
• 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들수 있는지 없는지, 있다면 push = + , pop = - 로 출력해야한다.

손으로 풀어보기

예제와 같이 임의의 수열 843687521 이 있다고 가정해보자,
첫번째로 들어온 8은 수열의 길이 이며, 1 ~ 8 까지의 수를 스택에 넣었다 뽑아 늘어놓음으로써, 나머지 43687521을 만들수 있는지 판별하면 될 것 같다.

1234=push*4
123 4=pop
12 3=pop
12 5=push
125 6=push
125 6=pop
125 7=push
1257 8=push
1257 8=pop
125 7=pop
12 5=pop
1 2=pop
1=pop

예제를 손으로 표현해보면 위와같을 것이다.
즉, 출력은 ++++--++-++----- 가 될 것이다.

슈도코드 작성하기

N(첫번째 줄 N 저장)
int[] 임의의 수열A = new int[]

for(N까지) {
	임의의 수열 저장
}

trigger 선언
스택 선언
int num = 1; // 1부터 스택에 넣었다 빼기위해...
for(N까지) {
	if(A[i] >= num) {}
		whlie(A[i] >= num) {
			push(num++);
			+ 버퍼저장
		}
		pop();
		- 버퍼저장
	} else {
		pop();
		if(A[i] < num) {
			NO 출력
			trigger 변경
		} else {
			- 버퍼저장
		}
	} 
} 

코드 구현하기

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.Stack;  
  
public class Main {  
  
    public static void main( String[] args ) throws IOException {  
       BufferedReader br = new BufferedReader( new InputStreamReader( System.in ) );  
       // BufferedWriter bw = new BufferedWriter( new OutputStreamWriter( System.out ) );  
       StringBuilder sb = new StringBuilder();  
       int N = Integer.parseInt( br.readLine() );  
       
       int[] A = new int[ N ];  
       for ( int i = 0; i < N; i++ ) {  
          A[ i ] = Integer.parseInt( br.readLine() );  
       }  
       Stack< Integer > stack = new Stack<>();  
       int num = 1;  
       boolean trigger = true;  
       for ( int i = 0; i < A.length; i++ ) {  
          if ( A[ i ] >= num ) {  
          
             while ( A[ i ] >= num ) {  
                stack.push( num++ );  
                sb.append( "+\n" );  
             }
	        stack.pop();  
            sb.append( "-\n" );  
            
          } else {  
             int top = stack.pop();  
             
             if ( top > A[ i ] ) {  
                trigger = false;  
                break;  
             } else {  
                sb.append( "-\n" );  
             }          
	    }
    } // for  
     
       if ( trigger ) {  
          System.out.println( sb );  
       } else {  
          System.out.println( "NO" );  
       }
       
    } // main
} // class