(JAVA) 백준 1874번 : 스택 수열

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

1874번: 스택 수열

문제

스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다.

1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라.

입력

첫 줄에 n (1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄부터 n개의 줄에는 수열을 이루는 1이상 n이하의 정수가 하나씩 순서대로 주어진다. 물론 같은 정수가 두 번 나오는 일은 없다.

출력

입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력한다. push연산은 +로, pop 연산은 -로 표현하도록 한다. 불가능한 경우 NO를 출력한다.

---

처음 풀어본 실버 3 문제이다. 

count라는 변수를 통해 스택에 넣을 1부터 n까지의 정수를 만들고,

함수를 통해 수열의 숫자 t값으로 스택에 어떤 작업을 할지 설정했다.

만약 count가 t값보다 작다면, 스택에 count를 push후 1씩 늘려줬다.

이후에 다시 함수를 호출해서 원하는 t값이 들어갈 때까지 count를 계속 늘려가며 push한다.

스택의 peek 메서드를 통해 스택 꼭대기에 t값이 있다면 pop해준다. 

t값이 스택 꼭대기 있는 값보다 작다면, 원하는 값을 찾을 때가지 pop 해줘야 하는데 

그 전에 t값이 스택 안에 있는지 확인하기 위해 contains 메서드를 사용한다.

 

디버깅 해가면서 하드 코딩으로 풀었는데, 솔직히 왜 맞았는지도 모르겠다...

처음에 찾고자 하는 값이 작아서 빼야 하는 상황에 contains를 통해 값이 없다면 예외를 발생시켰는데,

이러니까 시간 초과가 일어나 그냥 t값을 확인하는 부분에 포함시켰다.

사실 이러면 예외가 일어나지 않아서 만들 수 없는 수열에 NO가 발생하지 않는다.

테스트케이스를 5 - > 4 2 3 1 5 로 넣었을 시 3에서 NO가 나와야 하는 경우가 이에 해당되는데,

백준에서는 맞았다고 하는 게 신기하다. ㅋㅋㅋㅋ

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

public class B_1874  {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static int count = 1;
    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(br.readLine());
        Stack<Integer> st = new Stack<Integer>();
        try {
            for (int i=0; i<n; i++) {
                int t = Integer.parseInt(br.readLine());
                MyPop(t, st);
            }
        }
        catch (Exception e) {
            sb.setLength(0);
            sb.append("NO");
        }
        System.out.println(sb);
    }
    static void MyPop (int t,Stack<Integer> st) throws Exception {
        
        if (t>=count) {
            st.push(count);
            count++;
            sb.append(String.format("+%n"));
            MyPop(t, st);
        }
        else if (t<st.peek() && st.contains(t)) {
            st.pop();
            sb.append(String.format("-%n"));
            MyPop(t, st);
        }
        else if (t==st.peek()) {
            sb.append(String.format("-%n"));
            st.pop();                 
        }
    }    
}

 

출력 초과는 BufferdWriter 때문에 발생했다... 덕분에 StringBuilder 공부함.