[백준 | JAVA | 1874번] 스택 수열

 

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

📝 유튜브 풀이

https://www.youtube.com/watch?v=vf-i7Q_fN6w

• 첫 번째 줄에는 수열의 개수 N
• 두 번째 줄에서 N개의 줄에는 수열을 이루는 1이상 N이하의 정수가 1개씩 순서대로 주어지며 같은 정수가 두번이상 나오지 않는다.
• 오름차순 수열을 만들기 위한 연산 순서를 출력
  push 연산은 +, pop 연산은 -로 출력하고 불가능 할 때에는 NO 출력
• 1부터 자연수를 증가시키면서 입력으로 주어진 숫자와 비교하여 증가시킨 자연수를 스택에 추가하거나 빼는 방식으로 풀면 된다.

🔸 스택 연산 수행 방법

1. 자연수 <= 현재 수열 값

• 현재 수열 값이 자연수보다 크거나 같을 때까지 자연수를 1씩 증가시키면서 자연수 스택에 push. 그리고 push가 끝나면 수열을 출력하기 위한 마지막 1회만 pop
• 예를 들어 수열 값이 4인 경우, 스택에는 1, 2, 3, 4를 push하고 마지막에 1회만 pop하여 4를 출력한 뒤 조건문을 빠져나오며 자연수는 5가 된다.

2. 현재수열값 < 자연수

• 현재 수열 값보다 자연수가 크면 pop으로 스택에 있는 값을 꺼낸다.
  꺼낸 값이 현재 수열 값이거나 아닐 수 있다.
  만약 아니라면 후입선출 원리에 따라 수열을 표현 할 수 없으므로 NO를 출력 한 후 종료를하고 현재 수열 값이라면 그대로 조건문을 빠져나온다.
• 예를들어 수열 값이 4인 경우, 스택에는 1, 2, 3, 4를 push하고 마지막에 1회만 pop하여 4를 출력한 뒤 조건문을 빠져나오며 자연수는 5가 된다. 다음으로 현재 수열의 값은 3이므로 스택에서 3을 꺼낸다. 현재 수열 값과 스택 값에서 꺼낸 값은 같으므로 계속해서 스택 연산을 수행 할 수 있다. 스택에는 1,2가 남아있으며 자연수는 5이다.

🔸 슈도코드

N (수열 개수) A[] (수열 배열)

수열 배열 채우기

for(N만큼 반복){
	if(현재 수열값 >= 오름차순 자연수) {
    	while(값이 같아질 때 까지) {
        	push () 
            (+) 저장
        }
        pop ()
        (-) 저장
    } else ( 현재 수열값 < 오름차순 자연수) {
    	pop()
        if( 스택 pop 결과 값 > 수열의 수) {
        	No 출력
            } else {
            	(-) 저장
            }
    }
	if( - 값을 출력한 적이 없으면 ) 저장한 값 출력

import java.io.IOException;
import java.util.Scanner;
import java.util.Stack;
import java.util.function.BiConsumer;

public class Main {
    public static void main(String[] args) throws IOException {
    
    	Scanner scanner = new Scanner(System.in);
		
		//수열의 개수
		int N = scanner.nextInt();
		
		//수열의 개수만큼 배열 생성
		int A[] = new int [A];
		
		for (int i=0; i<N; i++) {
			A[i]= scanner.nextInt(); 
		}
		
		//스택 생성
		Stack<Integer> stack = new Stack<>();
		
		//오름차순으로 정렬해야하기때문에 1로 시작하는 변수 생성
		int num = 1;
		
		//break하여 빠져나오는 경우 체크하기위해 생성
		boolean result = true;
		
		StringBuffer bf = new StringBuffer();
		for(int i=0; i<A.length; i++) {
			
			//배열에 있는 수를 차례대로 가져온다.
			int su = A[i];
			
			//만약 배열에 있는 값이 현재 오름차순 자연수보다 큰 경우  
			if(num <= su) {
				
				//같아 질 때 까지 반복 
				while(num<=su) {
					
					//스택에 num 값을 push
					//num 값은 push할때마다 1씩 증가하기 때문에 num++
					stack.push(num++);
					
					//스택에 넣을때마다 + 를 출력해야하기 떄문에 stringBuffer에 + 저장
					bf.append("+\n");
				}
				
				//똑같아 졌을 때에는 마지막 하나를 가져와야하기때문에 pop
				stack.pop();
				
				//pop연산 할때마다 - 를 출력하기로 했으니 stringBuffer에 - 저장
				bf.append("-\n");
			} else {
				//만약 그렇지 않은 경우 (작거나 같은 경우) 하나 뺀다
				int n = stack.pop();
				
				/* 그런데 만약에 수열에 있는 값이 스택에 있는 마지막 값보다 크다면
				   오름차순으로 빼야 하기 때문에 스택을 완료할 수 없음.
				   그러므로 NO 출력 후 종료 */
				if(su < n) {
					System.out.println("NO");
					result = false;
					break;
				} else {
					//수열과 스택의 수가 같다면
					bf.append("-\n");
				}
			}
		}
		//만약 result 가 true라면 bf출력 
		if(result==true) {
			System.out.println(bf.toString());
		}
    }
}

    

📝 나의 풀이

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));
        
        int N = Integer.parseInt(br.readLine());
        
        //스택을 생성
        Stack<Integer> stack = new Stack<>();
        
        //출력할 결과물을 저장
        StringBuilder answer = new StringBuilder();

        int start = 0;

        for (int i = 0; i < N; i++) {
            int tmp = Integer.parseInt(br.readLine());

            if(start<tmp){
            	// start + 1부터 입력받은 tmp까지 push
                for (int j = start+1; j <= tmp; j++) {
                    stack.push(j);
                    // + 를 저장
                    answer.append('+').append('\n');
                }
                
                //다음 push 할 때 오름차순을 유지하기 위해 변수 초기화 
                start = tmp;
                
            } else if(stack.peek() != tmp){
            	//스택의 최상단 값이 입력받은 값과 같지 않을 경우 NO를 반환 및 종료 
                System.out.println("NO");
                return;
            }
            stack.pop();
            
            // - 를 저장 
            answer.append('-').append('\n');
        }
        System.out.println(answer);
    }
}