[알고리즘] 스택과 큐(백준 1874, 2164, 1927, 11286 -Java)

[알고리즘] 스택과 큐(백준 1874, 2164, 1927, 11286)

알고리즘 공부를 계속 미루는 제 자신을 보고 이대로는 안되겠다 싶어 😇
본격적으로 코딩테스트를 준비(+알고리즘 공부) 해보려고 합니다.
물론 혼자하면 작심삼일이 될거 같아
무료 Do it! 알고리즘 코딩테스트 with JAVA - 인프런 | 강의
강의 커리큘럼에 맞춰 공부해보자!!

[무료] Do it! 알고리즘 코딩테스트 with JAVA - 인프런 | 강의

자 모든 준비와 마음이 섰으니 기초부터 차근차근 공부해보자!

---

 

스택과 큐는 배열에서 발전된 형태의 자료구조 입니다.

스택과 큐 자료구조에 대해서 알아보시죠!

 

스택

스택을 쌓는다는 표현을 들어 보셨을 것 입니다.(특히, 게임 용어로 많이 등장 합니다. 🎮)

컴퓨터과학에서 정의하는 스택은 무엇을 의미할까요?
스택(stack)은 삽입(push)과 삭제(pop)연산이 후입선출(LIFO: Last In First Out)로 이뤄지는 자료구조 입니다.
쉽게 설명하면 바구니에 물건을 하나씩 쌓는다고 생각하면 됩니다.

바구니에 물건을 쌓다보면 제일 먼저 들어간 물건 제일 아래에 있습니다.
제일 마지막에(최근에) 넣은 물건이 제일 위에 있습니다.

이제 바구니에서 물건을 꺼낼 때를 생각해 봅시다.
바구니에 물건 3개를 넣었고, 제일 먼저 넣은 물건을 아이패드라고 합시다.
아이패드를 꺼내기 위해서는 아이패드 이후에 넣은 물건 4개를 먼저 꺼내야 합니다.

Push

스택에 새로운 데이터를 삽입하는 연산 입니다.

 

Pop

스택에 top데이터를 확인하고 삭제하는 연산 입니다.

 

Peek

스택에 top데이터를 확인하는 연산 입니다.

참고:
스택은 깊이 우선 탐색(DFS: Depth First Search), 백 트래킹 종류의 문제를 해결하는데 효과적 입니다.
또한 스택은 재귀 함수와 원리가 일맥상통 합니다.
알고리즘 재귀(Recursion -java)

[알고리즘] 재귀(Recursion -java)

큐

큐는 삽입(add)과 삭제(poll) 연산이 선입선출(FIFO: First In First Out)로 이뤄지는 자료구조 입니다.
삽입과 삭제가 양방향으로 이루어집니다.
빨대 모양이라고 생각하면 쉽습니다.

Add, Poll, Peek

rear쪽으로 새 값이 삽입(add)되고, font쪽으로 삭제(poll)가 이뤄집니다.
또한 font 쪽으로 peek 연산도 이뤄 집니다.

참고:
큐는 너비 우선 탐색(BFS: Breadth First Search)에서 자주 사용합니다.

우선 순위 (PriorityQueue)

값이 들어간 순서에 관계 없이 우선순위가 높은 데이터가 먼저 나오는 자료구조 입니다.
큐의 설정에 따라서 front에 항상 최댓값 혹은 최솟값이 위치 합니다.
우선 순위 큐는 일반적으로 힙(heap)을 이용해 구현하는데 힙은 트리 구조 중 하나 입니다.

참고:
힙(heap)은 우선순위 큐를 위해 고안된 완전 이진 트리 형태의 자료구조입니다.
여러 개의 값 중 최댓값 또는 최솟값을 찾아내는 연산이 빠릅니다.

참고:
완전 이진 트리는 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료구조입니다.
자식 노드를 각각 왼쪽 자식 노드와 오른쪽 자식 노드라고 합니다.

백준 1874

1874번: 스택 수열
테스트 케이스는 맞았는데, 제출하면 틀려서 애먹었다..ㅠ0ㅠ
2시간 넘게 고민했는데 결국 해결하지 못해 강의 설명을 보았다.!!
(스택에 관한 문제를 많이 풀어야겠다…)

 

문제 설명

• 현재 수열의 값 >= 자연수의 값
  먼저, 현재 수열의 값 보다 자연수의 값이 더 작거나 같다면 계속해서 push 해줘야 한다.
  push가 끝나면 수열을 출력하기 위해 pop을 1회 해준다.

 

e.g)
현재 수열의 값은 4이고, 자연수는 1부터 증가한다.
그러면 스택에 1, 2, 3, 4까지 push하고,
마지막에 pop을 해서 4를 꺼낸다. (문제에서 요구하는 현재 수열의 값(4)을 만족하게 되었기 때문!)

• 현재 수열의 값 < 자연수의 값
  현재 수열의 값보다 자연수의 값이 더 크다면 pop을 한다.
  그리고 pop한 값과 현재 수열의 값을 비교하여 pop한 값이 더 크다면 NO를 출력하고 애플리케이션을 종료!

 

e.g)
문제의 예제 입력 2를 참고하여 설명하면 다음과 같습니다.

 

 

 

 

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Quiz1874 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 수열이 담긴 배열
        int n = Integer.parseInt(br.readLine());
        int[] query = new int[n];
        for(int i = 0; i < n; i++) {
            query[i] = Integer.parseInt(br.readLine()); // 수열이 담긴 배열
        }

        /**
         * 1. 수열이 담긴 배열의 크기만큼 반복
         *  1-1. 만약 자연수의 값이 수열의 값보다 작거나 같으면
         *   1-1-1. 자연수의 값이 수열의 값보다 작거나 같을때까지 반복(num <= query[i])
         *    1-1-1-1. push(자연수++), result(+)
         *   1-1-2. pop, result(-)
         *  1-2. 그외
         *   1-2-1. pop
         *   1-2-2. 만약 pop한 값이 수열의 값보다 크면 NO
         *   1-2-3. 그외 result(-)
         */
        Stack<Integer> stack = new Stack<>();
        StringBuilder result = new StringBuilder(); // 단일스레드거나 동기화 고려X, StringBuffer는 멀티스레드 동기화 고려O
        int num = 1; // 자연수
        for(int i = 0; i < n; i++) {
            if(query[i] >= num) {
                while (query[i] >= num) {
                    stack.push(num++);
                    result.append("+\n");
                }
                stack.pop();
                result.append("-\n");
            } else {
                Integer pop = stack.pop();
                if(pop > query[i]) {
                    System.out.println("NO");
                    return;
                }
                result.append("-\n");
            }
        }

        System.out.println(result);

        br.close();
    }
}

 

결과
참고:
처음에는 result를 ArrayList<Character>로 출력했는데 시간이 엄청 오래걸렸습니다.
그래서 StringBuilder로 연산한 결과 시간이 1,200ms정도 줄었습니다.!!

백준 2164

2164번: 카드2
해결하는데 15분정도 걸릴거 같다.
큐의 개념만 알고있으면 쉽게 해결할 수 있습니다^^(FIFO를 기억하자!)

public class Quiz2164 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 카드 숫자
        int n = Integer.parseInt(br.readLine());
        // 카드 넣기
        Queue<Integer> q = new ArrayDeque<>();
        for(int i = 1; i <= n; i++) {
            q.add(i); // 4, 3, 2, 1
        }

        /**
         * 1. 맨위 카드 버리기(poll)
         * 2. 맨위 카드 아래에 넣기
         * 3. 1, 2 반복후 맨 마지막에 남는 카드 출력
         */
        while (q.size() > 1) {
            q.poll(); // 1 버림 4, 3, 2
            q.add(q.poll()); // 2를 맨아래에 넣음 2, 3, 4
        }
        System.out.println(q.poll());
    }
}

 

결과

백준 1927

1927번: 최소 힙
해결하는데 5분정도 걸린것 같다.
우선순위 큐의 개념을 알고 있으면 해결하기 쉬운 문제 입니다.
Java 에서 PriorityQueue의 기본 Comparator<T>는 오름차순으로 정렬하는 로직 입니다.
즉, PriorityQueue를 poll 하면 오름차순으로 값을 반환 합니다.

public class Quiz1927 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Queue<Integer> queue = new PriorityQueue<>();

        int n = Integer.parseInt(br.readLine());

        int x = 0;
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < n; i++) {
            x = Integer.parseInt(br.readLine());
            if(x == 0) {
                if(!queue.isEmpty()) {
                    sb.append(queue.poll()).append("\n");
                } else {
                    sb.append(0).append("\n");
                }
            } else {
                queue.add(x);
            }
        }

        System.out.println(sb);
    }
}

백준 11286

11286번: 절댓값 힙
혼자 해결하지 못했습니다.
이 문제의 핵심은 우선순위 큐(PriorityQueue)의 Comparator<T>에 대한 이해가 필요한 문제 입니다.
백준 1927를 응용한 문제입니다.
Java 에서 PriorityQueue의 기본 Comparator<T>는 오름차순으로 정렬하는 로직 입니다.
그러면 내림차순으로 정렬 하려면 어떻게 해야할까요? 🤔

 

내림차순 테스트

public class ComparatorTest {
    @Test
    void 내림차순_테스트() {
        int[] A = {1, 2, 10, -5, 0, 8};
        Queue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                if(o1 > o2) {
                    return -1;
                } else if(o1 < o2) {
                    return 1;
                }
                return 0;
            }
        });

        for(int i : A) {
            queue.add(i);
        }

        System.out.println(queue);

        for(int i = 0; i < A.length; i++) {
            System.out.print(queue.poll()+" ");
        }
    }
}

 

테스트 결과

10 8 2 1 0 -5

정렬 조건에 맞게 Comparator<T>를 직접 정의 해야합니다.

 

문제 조건
자 이제 문제 조건을 요약하면 다음과 같습니다.

1. 절댓값이 가장 작은 값부터 출력
2. 절댓값이 같으면 가장 작은수 부터 출력

Queue를 차례대로 꺼내면 위 조건에 부합해야 한다는 의미 입니다.
즉, 위 조건에 맞는 절댓값 정렬이 필요하기 때문에 우선순위 큐의 정렬 기준을 직접 정의 해야합니다.

 

풀이

public class Quiz11286 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 연산 갯수
        int n = Integer.parseInt(br.readLine());
        // x
        int[] x = new int[n];
        for(int i = 0; i < n; i++) {
            x[i] = Integer.parseInt(br.readLine());
        }

        /**
         * x가 0이 아닐 경우
         *  배열에 값 추가
         * x가 0인 경우
         *  만약 배열이 비어있는 경우 0을 출력
         *  배열에서 절댓값이 가장 작은 값 출력하고(여러개면 가장 작은 수 출력) 배열에서 제거
         */
        Queue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            /**
             * 1. 절대값이 같으면 가장 작은수 부터 출력(입력값 기준 오름차순)
             * 2. 절댓값이 가장 작은 값부터 출력(절댓값 기준 오름차순)
             */
            @Override
            public int compare(Integer o1, Integer o2) {
                // 절대값이 같으면 그중에서 작은 수로 오름차순
                if(Math.abs(o1) == Math.abs(o2)) {
                    return Integer.compare(o1, o2);
                }
                // 아니면 절대값이 작은 수로 오름차순
                else {
                    return Integer.compare(Math.abs(o1), Math.abs(o2));
                }
            }
        });

        StringBuilder sb = new StringBuilder();
        for(Integer v : x) {
            if(v == 0) {
                if(!queue.isEmpty()) {
                    sb.append(queue.poll()).append("\n");
                } else {
                    sb.append(0).append("\n");
                }
            } else {
                queue.add(v);
            }
        }
        System.out.println(sb);
    }
}

 

익명 클래스 대신 람다를 사용해도 됩니다.👍

Queue<Integer> queue = new PriorityQueue<>(
        (o1, o2) -> Math.abs(o1) == Math.abs(o2) ? Integer.compare(o1, o2) : Integer.compare(Math.abs(o1), Math.abs(o2))
);