백준 25556 포스택

첫 접근 방식 (오답)

4개의 스택으로 분리하지 않고 단순히 순열의 오름차순이 끊길 때마다 다른 스택에 담아야된다고 생각하여 스택 카운트를 증가시키고 스택 카운트 4초과시 NO를 출력하는 로직으로 구현.

 

잘못된 이유 : 한 번 오름차순이 끊기면 해당 스택을 재사용하지 않기 때문. 

 

구글링 이후에 다시 접근

1. 순열을 배열리스트에 담기 

ArrayList<Integer> numlist = new ArrayList<>();

for(int i=0; i<N; i++){
    numlist.add(sc.nextInt());
}

2. 4개의 스택 공간 생성 후 비교를 위한 초기값들을 넣어준다.

ArrayList<Stack<Integer>> stackList = new ArrayList<>();
for(int i=0; i<4; i++) {
    stackList.add(new Stack<>());
    stackList.get(i).add(Integer.MIN_VALUE);
}

 

3. 순열들의 수를 순서대로 스택에 담는 로직 구현 

cleanFlag => 청소 가능 여부    

placeInStack(num, stackList) => 해당 num을 stack 중 하나에 담을 수 있으면 true, 없다면 false

boolean cleanFlag = true;
for(int num : numlist){
    if(!placeInStack(num, stackList)){
        cleanFlag = false;
        break;
    }
}

 

4. 순열의 해당 수를 4개의 스택들 중 하나에 넣을 수 있는지 확인

i번째 stack의 꼭대기 값보다 순열의 수가 클 경우 스택에 담을 수 있다. 4개의 스택 어느곳에도 담을 수 없을 경우 false 리턴.

public static boolean placeInStack(int num, ArrayList<Stack<Integer>> stackList){
    for(Stack<Integer> stack : stackList){
        if(num > stack.peek()) {
            stack.push(num);
            return true;
        }
    }
    return false;
}

 

 

전체 코드

import java.util.ArrayList;
import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        int N;
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();

        ArrayList<Integer> numlist = new ArrayList<>();

        for(int i=0; i<N; i++){
            numlist.add(sc.nextInt());
        }

        ArrayList<Stack<Integer>> stackList = new ArrayList<>();
        for(int i=0; i<4; i++) {
            stackList.add(new Stack<>());
            stackList.get(i).add(Integer.MIN_VALUE);
        }

        boolean cleanFlag = true;
        for(int num : numlist){
            if(!placeInStack(num, stackList)){
                cleanFlag = false;
                break;
            }
        }

        System.out.println(cleanFlag ? "YES" : "NO");
    }

    public static boolean placeInStack(int num, ArrayList<Stack<Integer>> stackList){
        for(Stack<Integer> stack : stackList){
            if(num > stack.peek()) {
                stack.push(num);
                return true;
            }
        }
        return false;
    }
}