[알고리즘] 스택과 큐의 사용

스택과 큐를 사용한 문제 풀이

일반적으로 스택과 큐하면, 후입 선출과 선입 선출의 개념만 알면 끝 아닌가? 라는 생각을 할 수 있다.

하지만, 개념만 알아서는 되는 것이 아니라 실제로 어떻게, 어떠한 상황에서 사용하는 지 알아야 할 필요가 있다.

 

그 이전에 자바에서 사용되는 스택과 큐 메서드 용어를 정리해 두자.

 

<Stack>
top : 삽입과 삭제가 일어나는 위치
push : top 위치에 새로운 데이터를 삽입하는 연산
pop : top위치에 현재 있는 데이터를 삭제하고 확인하는 연산
peek : top위치에 현재 있는 데이터를 단순 확인하는 연산

<Queue>
rear : 큐에서 가장 끝 데이터를 나나냄
front : 큐에서 가장 앞의 데이터를 가리킴
add : rear 부분에 새로운 데이터를 삽입
poll : front부분에 있는 데이터를 삭제하고 확인하는 연산
peek : 큐의 맨 앞에 있는 데이터를 확인할 때 사용

 

 

스택을 사용하는 경우

 

물론 개인적인 생각이나 몇 가지 유형으로 나뉘는 듯 하다.

 

1. 문제 자체에서 스택을 사용하도록 유도하는 경우

2. 스택을 사용하여 문제를 간단하게 해결할 수 있는 경우

3. 스택을 사용할 때, 시간복잡도가 줄어드는 경우

 

예시 문제는 아래 백준 1874번과 같다.

1874번: 스택 수열

 

import java.io.*;
import java.util.*;

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

        int N = sc.nextInt();
        int[] A = new int[N];

        for (int i=0; i<N; i++) {
            A[i] = sc.nextInt();
        }

        Stack<Integer> stack = new Stack<>();
        StringBuffer bf = new StringBuffer();

        int num = 1;
        boolean result = true;

        for(int i=0 ; i< A.length; i++) {
            int su = A[i];
            if (su >= num) {
                while(su >= num) {
                    stack.push(num++);
                    bf.append("+\n");
                }
                stack.pop();
                bf.append("-\n");
            }
            else {
                int n = stack.pop();
                if (n > su) {
                    System.out.println("NO");
                    result = false;
                    break;
                }
                else {
                    bf.append("-\n");
                }
            }

        }

        if (result) System.out.println(bf.toString());
    }
}

 

이 문제는 요구 자체가 스택을 사용하여 해당 수열을 만들 수 있는 지를 묻는다.

즉, 후입 선출이라는 개념하에 조건에 부합할 시 push하고 pop하는 문제라는 것이다.

 

다음은 백준 17298문제이다.

17298번: 오큰수

 

해당 문제는 제한 시간이 1초이고, N의 최대 크기가 1,000,000이므로, 반복문을 사용하면 시간초과가 걸린다.

즉, 시간 복잡도를 줄이기 위해 스택을 사용할 수 있다.

 

후입 선출이라는 성질을 통해 시간복잡도를 출이거나, 특정 문제 조건에 대한 해결을 생각해보자

 

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(bf.readLine());
        int A[] = new int[N];
        int ans[] = new int[N];

        String[] str = bf.readLine().split(" ");
        for(int i=0; i<str.length; i++) {
            A[i] = Integer.parseInt(str[i]);
        }

        Stack<Integer> myStack = new Stack<>();
        myStack.push(0);

        // for(N만큼 반복)
        // while(스택이 비어있지 않고, 현재 수열의 값이 top에 해당하는 수열의 값보다 클 때까지)
        // { pop(), 정답 배열에 오큰 수를 현재 수열로 저장 }
        // 현재 수열을 오큰 수에 push
        for(int i=0; i<N; i++) {
            while(!myStack.isEmpty() && A[myStack.peek()] < A[i]) {
                ans[myStack.pop()] = A[i];
            }
            myStack.push(i);
        }

        // while(스택이 빌 때까지)
        // 스택에 있는 인덱스의 정답 배열에 -1 저장
        // 정답 배열 출력
        while(!myStack.isEmpty()) {
            ans[myStack.pop()] = -1;
        }

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for(int i=0; i<N; i++) {
            bw.write(ans[i] + " ");
        }
        bw.write("\n");
        bw.flush();
    }
}

 

 

해당 문제의 핵심은 스택을 인덱스처럼 사용하여, 불필요한 반복문을 줄인다는 것이다.

 

 

 

 

큐를 사용하는 경우

 

큐는 선입선출이라는 성질을 가지며, 스택과 마찬가지로 이를 유도하는 문제나 큐를 사용하였을 때 시간복잡도 및 풀이 방식이 간편화 되는 경우가 있다.

 

백준 2164번 문제를 살펴보자.

2164번: 카드2

 

이 문제는 Queue를 사용하면 정말 쉽다.

맨 위에 있는 큐 항목을 빼고, 그 다음 맨위의 큐 항목을 맨 아래에 추가하면 끝난다.

 

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        // N(카드 개수), myQueue(카드 저장 자료구조)
        // for(카드 개수만큼 반복)
        // { 큐에 카드 저장 }
        // while(카드가 1장 남을 때 까지)
        // { 맨 위의 카드 버리기, 맨 위카드를 가장 아래 카드로 이동 }

        Scanner sc = new Scanner(System.in);
        Queue<Integer> myQueue = new LinkedList<>();
        int N = sc.nextInt();
        for(int i=1; i<=N; i++) {
            myQueue.add(i);
        }
        while(myQueue.size() > 1) {
            myQueue.poll();
            myQueue.add(myQueue.poll());
        }
        System.out.println(myQueue.poll());
    }
}

 

 

 

우선순위 큐

우선 순위 큐는 큐 자료구조에서 우선 순위가 지정된 큐를 의미한다. 이는 값이 저장될 때, 정렬 순서를 지정해 줄 수 있다.

자바에서 우선순위 큐를 사용하여 정렬 순서를 지정해주는 방법은 간단하다.

 

Comparator를 사용하여 정렬 순서를 정해주었던 것처럼, PriorityQueue객체를 선언 할 때 순서를 정해주면 된다.

 

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        // N(질의 요청 개수)
        // 우선 순위 큐 선언
        // 절댓값 기준으로 정렬. 단 절댓값이 같다면, 음수 우선
        // for(N만큼 반복)
        // { 요청이 0이라면, 큐가 비어있으면 0 비어있지 않다면, 큐의 front값 출력
        // 요청이 1이라면, 새로운 데이터를 큐에 더하기 }

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(bf.readLine());
        PriorityQueue<Integer> MyQueue = new PriorityQueue<>((o1, o2) -> {
            int first_abs = Math.abs(o1);
            int second_abs = Math.abs(o2);
            if (first_abs == second_abs) {
                return o1 > o2? 1: -1;
            } else {
                return first_abs - second_abs;
            }
        });

        for(int i=0; i<N; i++) {
            int request = Integer.parseInt(bf.readLine());
            if (request == 0) {
                if (MyQueue.isEmpty()) {
                    System.out.println(0);
                } else {
                    System.out.println(MyQueue.poll());
                }
            } else {
                MyQueue.add(request);
            }
        }
    }
}

 

 

Reference

- Do it! 코딩 테스트 - 기초 편