스택 수열 1874 JAVA

 

이번 문제를 해결하기 위해선 규칙을 잘 파악해야 한다.

 

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

 

문제 자체는 간단하다고 생각하지만, 나는 이런 문제를 처음 봐서 약 20분동안 뭔 말인가 하고 문제를 들여다 보았다.

 

문제 해석과 풀이를 하자면 이와 같다.

1. 스택에 오름차순으로 수를 넣는다. 1,2,3,4,5,6,7 -> Possible     | |       4,6,7,1 -> Impossible

2. 입력값이 주어질 때, 현재 스택의 top이 같거나 크면 수열을 만들 수 있다.

3. 현재 스택의 top보다 입력값이 작다면 pop을 여러번 해야만 만들 수 있다. 따라서 이 경우는 스택을 만들 수 없다.

 

이 세 개만 알아도 이 문제를 구현해내는데 아무런 어려움이 없을거라 생각한다.

 

조금 더 자세하게 설명하자면, 입력된 수열이 4이고, 현재 아무 수도 스택에 넣지 않았다면

1~4까지 차례대로 넣고, top과 일치하면 pop()하면 된다. 그럼 현재 스택의 구조는 1,2,3이 될 것이다.

여기서 3보다 크다면 위의 과정을 반복하면 되고, 현재 top은 3인데 다음 수가 3이라면 단지 한번 더 pop을 하면 된다.

하지만, 1,2,3인 상태에서 다음 수가 1이라면 pop을 3번 해야 1을 꺼낼 수 있으므로 이 경우는 이미 4,3,2,1의 수열을 만들어버렸기에

4,1의 수열을 만들지 못한다. 이해가 되었다면 좋겠다.

 

 

 

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

public class Retry {
    static BiPredicate<Integer, Integer> p = Integer::equals;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        Stack<Integer> stack = new Stack<>();

        int N = Integer.parseInt(br.readLine());
        int lastNum = 0;

        while(!p.test(N--,0)) {
            int input = Integer.parseInt(br.readLine());

            while(true) {
                if(input > lastNum) {
                    stack.push(++lastNum);
                    sb.append("+").append("\n");
                }

                else if(p.test(stack.peek(),input)) {
                    stack.pop();
                    sb.append("-").append("\n");
                    break;
                }
                else {
                    System.out.println("NO");
                    System.exit(0);
                }
            }
        }
        System.out.println(sb);
    }
}

 

이건 그냥 람다식을 조금 이용해서 풀어본 거고, 람다식을 모른다면 아래 코드가 있다.

 

 

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

public class S1874 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb  = new StringBuilder();
        Stack<Integer> stack = new Stack<>();

        int n = Integer.parseInt(br.readLine()); // n을 입력 받는다. n은 수열의 개수이다.
        int lastNum = 0; // 스택에 마지막에 넣은 숫자

        while(n --> 0) {
            int num = Integer.parseInt(br.readLine());

            while(true) {
                if(lastNum < num) { // 마지막에 넣은 숫자보다, num 이 크다면 오름차순으로 증가시킨다.
                    stack.push(++lastNum);
                    sb.append("+").append("\n");
                }

                else if(stack.peek() == num) { // 일치하다면, lastNum 을 업데이트, pop 한다.
                    stack.pop();
                    sb.append("-").append("\n");
                    break;
                }
                else { // 이 경우는 stack의 top보다 num이 작은 경우이다.
                    System.out.println("NO");
                    System.exit(0);
                }
            }
        }
        System.out.println(sb);
    }
}