자료구조 공부 5/8 스택

연관문제 풀이

포스택 - 백준 25556번

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

// 1. 빈 스택이 있는지 여부를  boolean 변수로 체크하기 -> -> 스택에 0들을 넣음으로써 쉽게 처리
// 2. 스택의 최상단의 숫자 값과의 차이를 비교해서, 가장 적은 차이를 지닌 스택의 INDEX값을 저장하고, 루프가 끝난뒤 해당 스택에 값 넣기(-1 디폴트)
// 3. CUR 값보다 큰 수들만 스택에 있을 경우, 바로 NO 출력
// 4. 루프가 다 돌았을 때 이상 없다면 YES 출력\

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int size = Integer.parseInt(br.readLine());
        String[] input = (br.readLine()).split(" ");

        // 스택 초기화
        Stack<Integer>[] stacks = new Stack[4];
        for (int i = 0; i < 4; i++) {
            stacks[i] = new Stack<>();
            stacks[i].push(0);  // peek 할때나 emptyStackException을 편하게 처리하려고
        }

        int lowestDiffStackIndex = -1;
        int diff = Integer.MAX_VALUE;

        for (String s : input) {
            int n = Integer.parseInt(s);  // 넣어야 하는 숫자
            // 스택에 값 넣기
            for (int i = 0; i < 4; i++) {
                int cur = stacks[i].peek();

                if ((n - cur) < diff && (n - cur) > 0) {
                    diff = n - cur;
                    lowestDiffStackIndex = i;
                }
            }

            if (lowestDiffStackIndex == -1) {
                System.out.println("NO");
                return;
            } else {
                stacks[lowestDiffStackIndex].push(n);
            }

            // 변수 초기화
            diff = Integer.MAX_VALUE;
            lowestDiffStackIndex = -1;
        }

        System.out.println("YES");
    }
}

문제 풀이 전략은 두가지였다.
전략 1. 빈 스택은 최후에 최후에 사용한다
전략 2. 스택 최상단의 값의 차이가 가장 적은 곳에 넣는다.(가장 적은 차이로 작은 숫자가 스택에 있어야 한다)

그런데 빈 스택을 최후에 최후에 사용하는 것이 까다로웠다. 빈스택이 있는지도 체크해야 하고, 빈스택이 어디있는지도 파악해 두어야 하는 것이 귀찮았다.

이것을 빈 스택이 없게 만들기, 즉 모든 스택에 0 이라는 변수를 전부 넣어 놓음으로써 편하게 의도한 대로 코드를 짤 수 있었다.