Stack

Stack 이란

• Stack은 LIFO(Last-In-First-Out) 구조의 자료구조이다. 새로운 자료가 제일 위에 쌓이고, 가장 위에 있는 자료가 제일 먼저 나간다.

Stack의 구조

• Stack은 제일 위(Top)에서만 자료를 넣고 뺄 수 있으며, 가장 아래(Base)에서는 자료를 넣을 수는 없다.

Stack의 장단점

• Stack의 장점은 구조가 단순하여 쉽게 구현할 수 있으며, 데이터의 저장/삭제 연산이 빠르다. 단점으로는 가장 아래에 있는 자료에 접근하기 어렵다.

Java에서는 Stack 클래스를 지원한다.

주요 Method

• add(A): 스택에 A를 넣는다. //add는 boolean형을 리턴(true or false)

• push(A): 스택에 A를 넣는다. // push는 Exeption을 리턴

• pop(): 스택에서 맨 위에 있는 데이터를 꺼낸다.

• peek(): 스택에서 맨 위에 있는 데이터를 반환한다.

• search(A): 스택에서 A의 인덱스를 반환한다.

Overflow와 Underflow

1) Overflow

• 스택의 크기만큼 데이터가 꽉차서 데이터를 넣지 못할 때

2) Underflow

• 스택이 비어있을 때, 데이터를 꺼내려 하는 경우

스택 시간복잡도 Big O

• Insertion O(1)
• Deletion O(1)
• Search O(n)

삭제, 삽입시 맨 위에 데이터를 삽입, 삭제하기 때문에 시간복잡도는 늘 O(1) 이다. 하지만, 특정 데이터를 찾을 때는 특정 데이터까지 탐색 하므로, O(n) 의 시간 복잡도를 가진다.

예제문제

문제 : 포스택 (백준 25556번)

포닉스는 길이가 $N$인 순열 $A$와 네 개의 비어 있는 스택을 가지고 있다.

길이가 $N$인 순열이란, $1$ 이상 $N$ 이하의 서로 다른 정수 $N$개가 임의로 나열된 수열을 말한다.
스택이란 자료구조의 한 종류로 가장 나중에 삽입한 자료가 가장 먼저 나오는 후입선출 (Last In First Out, LIFO)의 특성을 가지고 있다.
포닉스는 PPC를 맞아 더러워진 순열을 청소하려 한다.

순열을 청소하는 것은 다음과 같은 과정을 통해 순열을 오름차순으로 정렬하는 것을 뜻한다. 즉 순열을 $1, 2, 3, \cdots N$으로 만들어야 한다.

순열 $A$의 원소들을 앞 원소부터 순서대로 네 개의 스택 중 하나에 삽입한다.
순열 $A$의 모든 원소를 스택에 삽입했다면, 네 개 중 원하는 스택에서 수를 꺼내는 것을 반복하여 네 개의 스택에서 모든 수를 꺼낸다.
꺼낸 수들을 꺼낸 순서대로 오른쪽에서 왼쪽으로 나열한다. 즉, 가장 처음에 꺼낸 수가 맨 뒤, 가장 나중에 꺼낸 수가 맨 앞에 위치하게 된다.
포닉스가 주어진 순열을 청소할 수 있는지 판별해 보자.

입력
첫째 줄에 순열의 길이 $N$이 주어진다. $(1 ≤ N ≤ 100\,000)$ 

둘째 줄에 순열 $A$의 원소 $A_i$가 공백으로 구분되어 주어진다. 모든 $A_i$는 $1$ 이상 $N$ 이하의 서로 다른 정수임이 보장된다.

예제 입력 1
10
4 3 6 7 8 9 10 2 1 5

예제 출력 1
YES

예제 입력 2
5
5 4 3 2 1

예제 출력 2
NO

나의 생각

• 주어진 스택은 4개
• 오름차순 1, 2, 3, 4 ~ , 9, 10 으로 정리가 가능한지 묻는, YES or NO 문제이다.
• 큰수를 마지막에 뽑아야하므로, 큰수들을 먼저 스택에 넣어야 한다.
• 문제에서 '꺼낸 순서대로 오른쪽에서 왼쪽으로 나열한다.'라고 했기때문
• 숫자가 들어오는 순서대로 스택에 나눠서 넣는다. (나누는 기준을 정의 해야한다.)
• 1번에서 4번 스택 순으로 탐색한다.
• 나누는 기준 : 들어갈 숫자는 스택에 이미 들어있는 숫자보다 커야한다.
• 위의 조건을 충족하면 스택에 넣고 break. 아닐시, 다음 스택에 자리를 알아본다.
• 만약 4개 스택 모두 들어갈 수 없다면 false를 리턴한다. => (count변수가 필요하겠구나)
• count변수를 만들어서 스택에 들어갈 수 있는 조건을 충족하지 못할 때마다 카운트한다.
• count가 4가 된다면 false를 return한다. 나머지 경우는 return true

구현

import java.util.*;

public class Main {
    public static void main(String[] args) {
    
    	// 스택을 리스트에 담아 관리하면 쉽게 구현할 수 있다고 생각했다.        
        List<Stack<Integer>> stackList = new ArrayList<>();


		// 입력 받기         
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(); 
        ArrayList<Integer> list = new ArrayList<>();
        for(int i=0;i<n;i++) 
        {
            list.add(in.nextInt());
        }

		// 처음 들어갈 숫자는 비교대상이 필요하다. 
        // 문제조건 :  '들어올 숫자는 1 이상 N 이하의 서로 다른 정수임이 보장된다' 
        // 4개의 스택에 미리 0을 넣어주고, 스택을 리스트에 담는다.        
        for(int i=0;i<4;i++)
        {
            Stack<Integer> stack = new Stack<>();
            stack.add(0);
            stackList.add(i,stack);
        }


		// solution함수가 true이면 YES, false이면 NO를 출력
        if(solution(stackList,list))
            System.out.println("YES");
        else
            System.out.println("NO");


    }
    //solution함수 : stack이 담긴 list와, 숫자를 입력받은 list를 받아온다.
    public static boolean solution(List<Stack<Integer>> stackList,ArrayList<Integer> list)
    {
        for(Integer num:list)
        {
            int cnt=0; // count 0으로 초기화
            for(int j=0;j<4;j++)
            {
                if(stackList.get(j).peek()<num) // 0~4번째 스택에 들어갈수 있을 때
                {
                    stackList.get(j).push(num); //해당 스택에 숫자를 push한다.
                    break;
                }
                else cnt++; //들어가지 못했다면 count += 1
            }
            if(cnt==4) // 4개의 스택에서 거절당했을 때
            {
                return false; // false를 리턴한다.
            }
        }

        return true; // 위 조건을 통과했다면 true를 리턴한다. 
    }
}

마무리

• 스택을 유지하면서 top의 값을 알고싶을 때, pop()대신 peek()을 사용하면 된다.
• class이름이 Main이 아닐 시, 컴파일오류가 발생한다. (백준사이트 제출 시)
• Stack을 이해하기 위해 Stack 클래스를 사용해보았다.
• 이 문제는 Stack 클래스를 List에 담아서 관리하지않고, 크기가 4인 Integer[] 만으로 풀 수 있다고 생각한다.
• Integer 배열의 값을 조건에 맞춰 스위칭하고, boolean을 이용하면 코드가 간결해 지고, 속도가 빨라진다.
• 또한, Scanner가 아닌, BufferedReader를 사용하면 속도가 더 빨라진다.

바로 해보자

import java.io.*;
import java.util.*;
import java.util.stream.Stream;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int a=Integer.parseInt(bf.readLine());
        Integer[] stack=new Integer[4];
        for(int i=0; i<4; i++) stack[i]=0;
        String[] numbers = bf.readLine().split(" ");
        boolean flag=true;
        for(int num: Stream.of(numbers).mapToInt(Integer::parseInt).toArray()){
            boolean cond=false;
            for(int j=0; j<4; j++){
                if(stack[j]<num){
                    stack[j]=num;
                    cond=true;
                    break;
                }
            }
            if(!cond){
                flag=false;
                break;
            }
            Arrays.sort(stack,Comparator.reverseOrder());
            //가장 큰수부터 비교하게끔 배열 정렬 !!!
        }
        System.out.println(flag?"YES":"NO");
    }
}

메모리는 늘었지만 시간을 단축시켰다!

Stream을 사용해보자

import java.io.*;
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        List<Integer> list = new ArrayList<>(n);
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            list.add(Integer.parseInt(st.nextToken()));
        }

        // 초기 스택 생성
        List<Stack<Integer>> stackList = IntStream.range(0, 4)
                .mapToObj(i -> new Stack<Integer>() {{
                    push(0);
                }})
                .collect(Collectors.toList());

        // solution 함수
        boolean result = list.stream()
                .map(num -> {
                    int cnt = 0;
                    for (Stack<Integer> stack : stackList) {
                        if (stack.peek() < num) {
                            stack.push(num);
                            break;
                        } else {
                            cnt++;
                        }
                    }
                    return cnt;
                })
                .noneMatch(cnt -> cnt == 4);

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