BOJ 1874번: 스택 수열

문제

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

1874번: 스택 수열

 

풀이

import java.util.*;
import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        Stack<Integer> iStack = new Stack<>();
        StringBuilder sb = new StringBuilder();

        int start = 1;

        for(int i=0;i<T;i++) {
            int n = Integer.parseInt(br.readLine());
            for(int j=start;j<=n;j++) {
                iStack.push(j);
                sb.append("+\n");
            }

			// 삡..
            if(start <= n) start = n+1;

            if(iStack.peek().equals(n)) {
                iStack.pop();
                sb.append("-\n");
            }
            else {
                System.out.println("NO");
                return;
            }
        }
        System.out.println(sb);
    }
}

 

1부터 n까지의 수를 스택에 넣고 빼고 하면서 주어진 임의의 수열이 나올 수 있는지 알아내야 한다.

• 1부터 n까지의 수를 차례대로(오름차순) 스택에 push한다.
• 첫번째 값을 찾기 위해 1부터 첫번째 값까지 스택에 push한다.
• 수열의 두번째 값부터는 또 1부터 push하면 안되고, 이전에 push했던 수 다음부터 push해야한다.
  • start라는 변수에 {마지막으로 push된 값+1}(다음값을 저장하기 위함)을 저장해둔다.
• 무조건 start에다가 마지막으로 push된 값을 저장해버리면 문제가 해결되지 않는다.
  
  • 예를 들어 수열의 첫번째 값이 4, 두번째 값이 3일 때,
    스택에 1,2,3,4가 push된 후 start에는 5가 저장된다.
    다음 for문에서는 적어도 5보다는 큰 숫자가 start에 저장되어야 하는데
    두번째 값이 3이라면 start에 4가 저장되기 때문에 if문으로 제한을 걸어줘야 한다.
• 스택에 마지막으로 push된 값과 수열에서 찾고자 하는 값이
  • 같다면 스택에서 pop 한다.
  •  다르다면 주어진 수열은 만들 수 없기 때문에 NO를 출력한다.

 

 

---

이번 문제는 테스트 케이스는 잘 통과가 되는데 제출이 계속 안돼서 힘들었다.
IDE에서 디버깅을 해봐도 반례를 뭘 넣어봐야 할지 몰라서 애타고 있었는데,,

같이 공부하시던 분이 그냥 1 2 3 4 5 6을 넣어보라 하셔서 넣어보니까 바로 오답이 나왔다,,!

 

if(start <= n) start = n+1; 

 

이 부분을,

 

if(start < n) start = n+1;

 

이렇게 적고 있었어서 문제 해결이 안됐었는데 바로 해결해주셨따.