[Gold V] 백준 - 25556. 포스택 : Java

25556번: 포스택

 

 

이해하기

처음 문제를 읽었을 때, 문제 내용 중 '순열 청소'에 대해 이해가 잘 안 됐다. 

예제 1을 가지고 다시 이해한 내용은 아래와 같다.

 

꺼냈을 때 오름차순이 될 수 있도록 스택 4개에 나눠 저장할 수 있다면 "YES", 그렇지 않으면 "NO"를 출력하면 된다.

 

스택은 top에서부터 데이터를 꺼내는데, 위 메모에서는 스택의 맨 오른쪽이 top이라고 본다. 한 번 꺼내보자.

9 → 8 → 7 → 6 → 5 → 4 → 3 → 2 → 1

이 순열은 4개의 스택을 이용해서 오름차순이 가능한 순열이다.

 

예제 2도 한 번 생각해보자.

 

이렇게 적어보면 1이 갈 곳이 없다. 스택 1에 1이 들어간다면 5보다 1이 먼저 나와 5의 오른편에 있게 되니 오름차순이라고 할 수 없다. 스택 2, 3, 4도 마찬가지이다. 그렇기에 이 순열은 "NO"가 출력되어야 하는 것이다.

 

 

문제 풀이

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

public class no_25556_re {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] A = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        Stack<Integer>[] stacks = new Stack[4];
        for (int i = 0; i < stacks.length; i++) {
            stacks[i] = new Stack<>();
            stacks[i].push(0);
        }

        for (int i = 0; i < N; i++) {
            boolean flag = false;
            for (int j = 0; j < stacks.length; j++) {
                if (stacks[j].peek() < A[i]) {
                    stacks[j].push(A[i]);
                    flag = true;
                    break;
                }
            }

            if (!flag) {
                System.out.println("NO");
                return;
            }
        }
        System.out.println("YES");
    }
}

 

코드는 이렇게 작성하였는데 하나하나 뜯어서 분석해보자!

 

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

 

Scanner가 아니라 BufferedReader를 사용한 이유는 시간 차이 때문이다. Scanner보다 BufferedReader가 더 빠르기에 사용했다.

자바(JAVA) - Scanner & BufferedReader

 

int N = Integer.parseInt(br.readLine());
int[] A = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

 

readLine()은 String으로 받아오기 때문에 각각 변환을 해주었다.

배열 A는 stream을 사용해보았는데 아직 익숙하지 않아서 바로바로 생각이 안 난다.🥹

 

Stack<Integer>[] stacks = new Stack[4];
        for (int i = 0; i < stacks.length; i++) {
            stacks[i] = new Stack<>();
            stacks[i].push(0);
        }

 

문제에서 스택이 4개라고 했으니 스택 배열 사이즈를 4로 하였다.

for문에서 스택 4개를 각각 생성해주고 0을 넣어주었다.

 

이 때 0을 넣어준 이유는, 문제에 "길이가 N인 순열이란, 1 이상 N 이하의 서로 다른 정수 N개가 임의로 나열된 수열을 말한다."라는 내용이 있었기 때문이다. 순열 A 내의 정수들은 1 이상이기에 어떤 숫자도 0보다는 클 것이다. 앞으로 스택에 들어올 숫자들을 비교해주기 위해 미리 0을 넣은 것이다.

 

for (int i = 0; i < N; i++) {
	boolean flag = false;
	for (int j = 0; j < stacks.length; j++) {
		if (stacks[j].peek() < A[i]) {
			stacks[j].push(A[i]);
			flag = true;
			break;
		}
	}

	if (!flag) {
		System.out.println("NO");
		return;
	}
}
System.out.println("YES");

 

for문을 i = 0 부터 i = N - 1까지 i++ 하면서 돌린다.

boolean 형태의 flag를 false로 선언해주었다.

내부에 for문을 하나 더 작성하여 j = 0 부터 j < stacks.length - 1 (= 3)까지 j++하며 돌려준다.

만약 4개의 스택 중에서 peek() 해온 값이 A[i]보다 작다면 해당 스택에 A[i]를 push()한 후 flag를 true로 바꾸고 break해준다.

 

만약 flag가 한 번이라도 false라면, 4개의 스택 중 어떠한 스택에도 해당 숫자를 넣지 못한 것이기 때문에 NO를 출력해야 한다. if(!flag == true) 이기에 NO를 출력한 후 리턴한다.

 

flag가 계속 true였다면 YES를 출력한다.

 

이 이중 for문 부분이 이해하기가 어렵기 때문에 예제 2를 가지고 다시 정리해보았다.

 

직접 적어가며 생각해보니 조금 더 풀리는 느낌이다. 앞으로 갈 길이 멀다!