[임시] 스택과 큐

 

이론

 

스택

pop은 삭제하고 확인, peek은 단순 확인만

깊이 우선 탐색(DFS), 백트래킹에 효과적. 후입선출은 재귀 함수 원리와 일맥상통하기 때문

물론 스택보다 재귀를 좀 더 쓰긴 함

그래도 구조가 특이해서 가끔 응용문제가 나오니, 원리만 잘 알아두기

 

큐

선입선출, 양방향에서 삽입과 삭제

추가는 큐의 rear에서, 삭제는 큐의 front에서

너비 우선 탐색(BFS) 구현할 때 자주 사용

 

큐랑 스택은 배열의 확장판

큐랑 스택은 자료구조 자체를 이용하기도 하지만,

개념을 이해하고 이에 따라 문제 푸는 경우 많음

=> 후입선출, 선입선출 두 원리만 잘 이해하면 됨

 

우선순위 큐

들어간 순서 상관없이 우선순위가 높은 데이터가 먼저 나오는 자료구조

front에 따라 항상 최댓값 또는 최솟값 위치

힙을 이용해 구현함

 

관련 문제

[java] 문제 011(백준 1874)

 

[java] 문제 012 (백준 17298)

 

[java] 문제 013 (백준 2164)

 

[java] 문제 014 (백준 11286)

 

 

풀기 전 문제 개념 쭉 훑어보면서 기록한 내용

 

문제 11, 스택 수열, 1874번

오름차순은 작은 것부터 큰 순으로, 내림차순은 큰 것에서 작은 순으로

스택에 push하는 순서는 반드시 오름차순을 지키도록 한다

=> PUSH는 무조건 작은 숫자가 먼저

임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지 

=> 입력한 수열을 그대로 출력하기

 

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

stack.pop();

 

StringBuffer bf = new StringBuffer();

bf.append("+\n");

System.out.println(bf.toString());

 

---

문제 12, 오큰수, 17298번

스택의 후입선출이 실마리일 때가 있음.

종종 시간 복잡도를 줄이거나 특정한 문제 조건을 손쉽게 해결하는

=> 문제에 접근할 때 혹시 스택을 이용하면 손쉽게 풀리지 않는지 한 번쯤 고민해보세요

 

int[]A = new int[n];    // 수열 배열 생성

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

=> split 메소드란 게 있구나, 그렇게 중요한 부분은 아니고

 

myStack.push(0);

=>

 

//스택 비어있지 않고 현재 수열이 스택 TOP인덱스 가르키는 수열보다 크면
        while (!myStack.isEmpty() && A[myStack.peek()] < A[i]) {  
            ans[myStack.pop()] = A[i];  //정답 배열에 오큰수를 현재 수열로 저장하기
        }

=> 스택에 isEmpty() 가 있구나, myStack.peek()이 있구나

 

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

=>  BufferedWriter는 이런 식으로 쓰는 구나, 물론 그리 중요한 부분은 아니고, 어거지로 다른 입출력 함수 써도 됨

 

---

문제 13, 카드2, 2164번

가장 위의 카드를 가장 아래에 있는 카드 밑으로 옮기는 동작

=> 큐의 선입선출 성질 이용하면 쉽게 구현 가능

 

Queue<Integer> myQueue = new LinkedList<>();

=> 큐는 링크드리스트로 해주구나

---

문제 14, 절댓값 힙, 11286번

 

N의 최대 범위가 100000이므로 O(nlogn) 시간 복잡도 알고리즘으로 풀 수 있다?

=> 시간 복잡도 종류는 logn -> n -> nlogn -> n의 제곱 -> 2의 n제곱 -> n!

=> 이걸 머릿속에 딱 박아둔 다음, 만약 n의제곱이면 10의 10제곱으로 1억을 훌쩍 넘음, 그러니 그 아래 단계인 nlogn 사용 가능 느낌으로 접근

 

데이터가 새로 삽입될 때마다 절댓값과 관련된 정렬 필요하므로 우선순위 큐로 문제 쉽게 해결 가능

단, 이 문제는 절댓값 정렬이 필요해서 우선순위 큐의 정렬기준을 직접 정의해야 함

 

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;// 절대값을 기준으로 정렬
    });

=> 이 PriorityQueue는 절대값을 기준으로 정렬하며, 절대값이 같은 경우에는 음수 값을 우선으로 정렬합니다.

=> new PriorityQueue<>((o1, o2) -> {...}): 람다 표현식을 사용하여 사용자 정의 비교자를 제공합니다.

=> Math.abs(o1); // 절대값 처리

=> return first_abs - second_abs;: 절대값을 기준으로 정렬합니다. 절대값이 작은 숫자가 먼저 오도록 합니다.

 

사용자 정의 비교자 (Comparator)

Comparator 인터페이스를 구현하는 가장 일반적인 방법은 익명 클래스 또는 람다 표현식을 사용하는 것입니다. 이 인터페이스에는 compare라는 메소드가 있으며, 두 개의 객체를 비교하여 정수 값을 반환합니다:

PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer 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; // 절대값 기준 정렬
                }
            }
        });

 

=> 위 에제처럼 사용자 지정 비교자를 사용 안 하면, 기본적으로 자연 순서(오름차순)로  정렬합니다.

=> 비교자가 양수를 반환하면 스왑하고, 음수를 반환하면 스왑을 안 함

즉 기본은 오름차순 정리임. 두 요소가 있다고 치자고. {3, 5}가 있고 3이 first, 5가 second임. 순서가

보통 앞에 거 - 뒤에 거, 즉 first-second를 해서 first가 크지? 하지만 기본적으로 정렬 알고리즘은 다 오름차순이 디폴트임.

그러니 앞에 거 크니 양수를 반환하고, 그러니 오름차순으로 정리하기 위해 두 객체를 스왑해서 작은 게 앞에 놓는 거임