[백준: 알고리즘_Java] 1874번_스택 수열

 

<문제>

 

이건 문제를 이해하는 데도 약간의 시간이 필요했음...

그니까 첫 번째로 입력받는 숫자는 수열을 뽑는 스택의 크기가 될 것임.

그리고 다음으로 계속 입력받는 수들은 우리가 스택에 추가하고 뽑아야 될 수. (뭐래는거야..)

 

아무튼 간단하게 예를 들면 4라는 수가 처음 주어졌을 때, 

순서대로 3 2 1 4를 입력했다고 치면

스택에 적절히 push, pop을 하면서 pop할 때 나오는 수가 순서대로 3 2 1 4가 되도록 하는 것임.

(stack에 push할 때는 오름차순만 가능)

push하면 +출력, pop하면 -출력

 

 

내가 진짜 이 문제 2시간동안 푼 듯..

구글에 풀이 검색하고 싶은 거 꾹 참음.

---

<풀이>

처음엔 Scanner와 Bufferedwriter를 이용했는데, 버퍼의 마지막 개행문자때문에 출력초과가 떠서 버퍼 대신 StringBuilder 사용함. -> 마지막 개행문자 .trim()으로 없앨 수 있음.

 

import java.util.*;
public class Sequence {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();
        Stack<Integer> stack = new Stack<>();

        int num = sc.nextInt();
        int[] inarr = new int[num];

        //배열에 수열 저장
        for(int i = 0; i< num; i++) {
            inarr[i] = sc.nextInt();
        }

        //inarr[j] > i 이면,
        //(inarr[j]==i 될 때 까지) push(i), i++;
        //같아지면 pop(), j++ i++
        //inarr[j] < i 이면,
        //pop()한 값 == inarr[j] 될 때까지 pop (stack 빌 때까지 안 같아지면 'NO', 전체 종료)
        int i = 1;
        int j = 0;
        boolean flag = true;

        try {

            loop1:
            while (true) {
                if (j >= num) break;
                if (inarr[j] > i) {
                    while (inarr[j] != i) {
                        stack.push(i);
                        sb.append("+\n");
                        i++;
                    }
                } else if (inarr[j] == i) {
                    stack.push(i);
                    sb.append("+\n");
                    i++;
                    stack.pop();
                    sb.append("-\n");
                    j++;
                } else if (inarr[j] < i) {
                    while (true) {
                        try {
                            int k = stack.pop();
                            sb.append("-\n");

                            if (inarr[j] == k) {
                                j++;
                                break;
                            }
                        } catch (Exception e) {
                            System.out.println("NO");
                            flag = false;
                            break loop1;
                        }

                    }
                }
            }
            if (flag) {
                System.out.print(sb.toString().trim());

            }
        }catch (Exception e) {
            e.printStackTrace();
        }

    }


}

---

<결과>

 

출력 초과 이유는 마지막 개행문자 안 없애서..

컴파일 에러는 븅신같이 C++로 제출함. 그래놓고 이거 왜이러지 이러면서 구글링까지함.