[Java] 백준 1874번 : 스택 수열

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

1874번: 스택 수열

 

[접근]

(stack 을 이용한 설명)

- 몇번 까지 넣었는지 저장하는 number

- 받아온 입력값 stackNum

 

딱 두가지의 경우가 있다.

 

1.  stackNum > number 인경우 ) 값을 number +1 부터 stackNum까지 스택에 넣어주고 마지막에 stackNum을 pop을 해준다.

그리고 number = stackNum 을 해주어서 몇번까지 집어 넣었는지 갱신해준다.

2. 아닐 경우는 pop 을 해주어야한다. 여기서  pop을 할때 가져온stackNum와 stack.peek() 값이 같을때 pop을 할 수 있다. 그렇지 않으면 문제에서 제시한 수열을 만들 수 없으므로 return 을 하던가  exit(0) 를 해준다.

 

[코드 - Stack  자료 구조 이용]

 

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

public class Main1874{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());
        Stack <Integer>  stack = new Stack<>();

        int number =0;

        while (N-->0){

            int stackNum = Integer.parseInt(br.readLine());

            if (number <stackNum){
                for (int i = number+1 ; i <=stackNum;i++){
                    stack.push(i);
                    sb.append("+\n");
                }
                number = stackNum;

            }else if(stack.peek()!=stackNum){
                System.out.print("NO");
                System.exit(0);
            }

            stack.pop();
            sb.append("-\n");
        }

        System.out.println(sb);

    }
}

 

 

[코드 -배열 이용] 배열을 이용하여 풀면 시간을 좀 더 단축 시킬 수 있다.

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

public class Main1874 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int N = Integer.parseInt(br.readLine());
        int []stack = new int[N];

        int number =0;
        int index= 0;

        while (N-->0){

            int stackNum = Integer.parseInt(br.readLine());

             if (number <stackNum){
                 for (int i = number+1 ; i <=stackNum;i++){
                     stack[index]= i;
                     index++;
                     sb.append("+\n");
                 }
                 number = stackNum;

             }else if(stack[index-1]!=stackNum){
             System.out.print("NO");
             System.exit(0);
             }

             index--;
             sb.append("-\n");
        }

            System.out.println(sb);

    }
}