백준 1874번 스택 수열 자바[java]

• 스택 수열

1874번: 스택 수열

 

처음 봤을땐 무슨 소리인지 몰라서 구글링으로 문제를 이해했다.

 

정리해보자면 스택에 숫자는 오름차순(1,2,3,4,,,)으로 들어간다.

스택에 넣어주고 빼는 과정에서 

입력할때 받은 숫자들의 순서대로 나올 수 있다면 "+", "-"로 표현하고

그렇지 않다면 "NO" 출력한다. 

이때 스택에 넣어주는 것은 "+"

빼주는 것은 "-"로 표현한다.

 

예를들어 

8
4
3
6
8
7
5
2
1

이렇게 입력받았다면

처음 8은 앞으로 8개의 숫자가 입력됨을 의미.

4가 나왔으므로

스택에 순서대로 1,2,3,4를 넣는다.

그리고 (stack.peek() == 입력받은 값) 비교를 통해 

pop()여부 결정. 

다음입력은 3이다.

이전에 받았던 값보다 작은 값이므로

이미 스택에 들어가 있을 것이다.

그러므로 스택에 숫자를 넣는 과정은 생략.

(stack.peek() == 입력받은 값 3)비교를 통해

pop()여부 결정.

 

스택에 1,2,3,4 까지 넣었었다.

다음에 넣을땐 5부터 넣으면 되는데

이를 코드로 포현해서

위 과정들을 끝까지 반복하면 된다.

 

결과로 나온 "+"와"-"를 한 번에 출력해야하므로 StringBuilder를 이용했다.

import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.*;
public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc= new Scanner(System.in);
        StringBuilder sb = new StringBuilder();
        Stack<Integer> stk = new Stack<>();
 
        int N = sc.nextInt();
        int start = 0;
 
        while(N-- > 0){
            int value = sc.nextInt();
 
            if(value > start) {
                for (int i = start + 1; i <= value; i++) {
                    stk.push(i);
                    sb.append("+\n");
                }
                start = value;
            }
 
            if(stk.peek() != value){
                System.out.println("NO");
                return;
            }else{
                stk.pop();
                sb.append("-\n");
            }
        }
        System.out.println(sb);
    }
}