[백준] 1874번 스택 수열(JAVA)

문제

- 스택은 자료를 넣는(push) 입구와 자료를 뽑는(pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 LIFO(Last int First out) 특성을 가짐

- 1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있음

- 스택에 push하는 순서는 반드시 오름차순을 지킴

- 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지 판단

- 만들 수 있다면 어떤 순서로 push와 pop 연산을 수행하는지 계산(push : + / pop : -)

 

해결방법

java의 stack 클래스를 사용하여 문제를 해결하였다.

스택에 push할 때, 이전에 push 되었던 수를 또 넣을 순 없기 때문에 이전에 넣었던 최대값을 저장해두고 그 값 이상의 숫자를 원할 때만 push할 수 있도록 코드를 작성하였다.

stack에서 pop을 할 때, stack 내에 해당 숫자가 있는지 확인할 수 있도록 stack 클래스에 있는 search() 메서드를 활용하였다. stack.search(...) 메서드는 해당 stack 내부에 존재한다면 존재하는 인덱스를, 존재하지 않는다면 -1을 반환한다. 이를 활용하여 stack 내부에 숫자가 있는지 확인하고 pop 연산을 수행할 수 있도록 하였다.

 

코드

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        int n = Integer.parseInt(br.readLine());
        Stack<Integer> stack = new Stack<>();
        
        int max = 0;	// stack에 중복되지 않은 Push 연산을 수행하기 위해서 이전까지 들어갔던 숫자의 최대값 저장 
        int min = 0;

        for(int i = 0; i<n; i++){
            int num = Integer.parseInt(br.readLine());		// stack에서 꺼낼 수
            if(max<num) {	// max 값보다 크다면 이전에 들어간 적이 없는 숫자이기 때문에 Push 연산 수행
                max = num;
                
                // 이전에 들어갔던 수보다 큰 수부터 현재 숫자까지 Push 연산 수행
                for(int j = min+1; j<=max; j++){
                    stack.push(j);	
                    sb.append("+").append("\n");
                }
                
                min = max;
            }
	
    	    // stack 내부에 해당 숫자가 존재하는지 검사
            if(stack.search(num) != -1){
            	// 해당 숫자가 Pop될 때까지 Pop 연산 수행
                while(stack.size()>0 && stack.peek() >= num){
                    stack.pop();
                    sb.append("-").append("\n");
                }
            }else if(stack.search(num) == -1){
            	// 존재하지 않는다면 "NO" 출력
                sb = new StringBuilder();
                sb.append("NO");
                break;
            }

        }
        System.out.println(sb);
        br.close();
    }
}