[백준] 25556번 : 포스택

📚 문제

이미지를 클릭하시면 문제 링크로 연결됩니다.

---

📝 문제 이해

• 길이가 N인 순열 A의 원소들을 순서대로 네 개의 비어있는 스택에 쌓는다.
• 스택을 끝에서부터 꺼냈을 때 오름차순으로 나열하게 만들면 된다.

---

💡 문제 풀이

• StringTokenizer 클래스를 활용해 띄어쓰기를 구분해준다.
• 토큰 객체를 루프를 돌려서 배열에 저장해준다.
• 배열의 앞 부분부터 스택에 저장해준다.
• 이 때, 조건은 스택의 peek 보다 배열이 큰 수라면 스택에 저장하도록 한다.
• 스택에 쌓았다면 루프를 탈출해 다음 배열의 수로 넘어간다.
• 만약 루프를 돌던 중 스택의 peek 보다 배열이 큰 수가 없다면 청소할 수 없으므로 "NO" 를 출력한다.

---

💻 소스 코드

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

public class beak25556 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));   // 번호 입력
        int n = Integer.parseInt(br.readLine());    // 길이가 n 인 순열을 만들기 위한 변수 선언
        StringTokenizer st = new StringTokenizer(br.readLine());    // 문자열 분리
        int[] arr = new int[n];     // 길이가 n 인 순열을 만들기 위한 배열 선언

        // arr 배열에 입력받은 번호 저장
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());  // 토큰에서 하나씩 꺼내서 배열에 저장
        }

        Stack<Integer>[] stacks = new Stack[4];     // 네 개의 비어 있는 스택 0으로 초기화
        for (int i = 0; i < 4; i++) {
            stacks[i] = new Stack<>();
            stacks[i].push(0);
        }

        for (int i = 0; i < n; i++) {
            boolean chk = false;
            for (int j = 0; j < 4; j++) {
                if(stacks[j].peek() < arr[i]){  // 스택의 peek 보다 배열이 큰 수라면 스택에 저장
                    stacks[j].push(arr[i]);
                    chk = true;
                    break;      // 스택에 쌓았다면 루프 탈출
                }
            }

            if(!chk){   // 루프를 돌던 중 스택의 peek 보다 배열이 큰 수가 없다면
                System.out.println("NO");
                return;
            }
        }

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