스택과 큐

스택 : 깊이 우선 탐색 (DFS:Depth First Search), 백트래킹 종류의 코딩 테스트에 효과적. 후입선출은 개념 자체가 재귀 함수 알고리즘 원리와 일맥상통.

 

큐 : 너비 우선 탐색 (BFS:Breadth First Search)에서 자주 사용

---

 

[백준 1874번] 스택 수열

https://www.acmicpc.net/problem/1874

 

스택 연산 수행 방법
1. 현재 수열 값 >= 자연수
현재 수열 값이 자연수보다 크거나 같을 때까지 자연수를 1씩 증가시키며 자연수를 스택에 push한다. 그리고 push가 끝나면 수열을 출력하기 위해 마지막 1회만 pop한다.
예를 들어 현재 수열 값이 4면 스택에는 1, 2, 3, 4를 push하고 마지막에 1회만 pop하여 4를 출력한 뒤 조건문을 빠져나온다. 자연수는 5가 된다.

2. 현재 수열 값 < 자연수
현재 수열 값보다 자연수가 크다면 pop으로 스택에 있는 값을 꺼낸다. 꺼낸 값이 현재 수열 값이거나 아닐 수 있다. 만약 아니라면 후입선출 원리에 따라 수열을 표현할 수 없으므로 NO를 출력한 후 문제를 종료하고, 현재 수열 값이라면 그대로 조건문을 빠져나온다.
앞의 예를 이어 설명하면 자연수는 5, 현재 수열 값은 3이므로 스택에서 3을 꺼낸다. 현재 수열 값과 스택에서 꺼낸 값은 같으므로 계속해서 스택 연산을 수행할 수 있다. 스택에는 1, 2가 남아 있으며, 자연수는 5다.

 

 

[정답]

package algorithm;

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 < N; i++) {
            int su = A[i];      // 현재 수열의 수
            if(su >= num) {     // 현재 수열 값 >= 오름차순 자연수 : 값이 같아질 때까지 push() 수행
                while(su >= num) {  // push()
                    stack.push(num++);
                    bf.append("+\n");
                }
                stack.pop();
                bf.append("-\n");
            }
            else {      // 현재 수열 값 < 오름차순 자연수 : pop()을 수행해 수열 원소를 꺼냄
                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());
    }
}

 

---

 

[백준 17298번] 오큰수

https://www.acmicpc.net/problem/17298

 

설명 굉장히 잘 되어 있음 참고

https://st-lab.tistory.com/196

[백준] 17298번 : 오큰수 - JAVA [자바]

 

[정답]

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Stack<Integer> stack = new Stack<>();

        int N = Integer.parseInt(br.readLine());
        int[] seq = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            seq[i] = Integer.parseInt(st.nextToken());
        }

        for (int i = 0; i < N; i++) {
            while(!stack.isEmpty() && seq[stack.peek()] < seq[i]) {
                seq[stack.pop()] = seq[i];
            }
            stack.push(i);
        }

        while(!stack.isEmpty()) {
            seq[stack.pop()] = -1;
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++) {
            sb.append(seq[i]).append(' ');
        }
        System.out.println(sb);
    }
}

 

---

 

[백준 2164번] 카드2

https://www.acmicpc.net/problem/2164

 

1. poll을 수행하여 맨 앞의 카드를 버린다.
2. 과정 1에 이어 바로 add를 수행해 맨 앞에 있는 카드를 가장 아래로 옮긴다.
3. 큐의 크기가 1이 될 때까지 과정 1~2를 반복한 후 큐에 남은 원소를 출력한다.

 

[정답]

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

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());
        Queue<Integer> queue = new LinkedList<>();

        for (int i = 1; i <= N; i++) {  // 카드를 큐에 저장
            queue.add(i);
        }
        while(queue.size() > 1) {   // 카드가 1장 남을 때까지
            queue.poll();           // 맨 위의 카드를 버림
            queue.add(queue.poll());    // 맨 위의 카드를 가장 아래 카드 밑으로 이동
        }
        System.out.println(queue.poll());  // 마지막으로 남은 카드 출력
    }
}

 

---

 

[백준 11286번] 절댓값 힙

https://www.acmicpc.net/problem/11286

 

N의 최대 범위가 100,000으로 O(nlogn) 시간 복잡도를 가진 알고리즘으로 풀 수 있다. 데이터가 새로 삽입될 때마다 절댓값과 관련된 정렬이 필요하므로 우선순위 큐로 문제를 쉽게 해결할 수 있다. 단 이문제는 절댓값 정렬이 필요하므로 우선순위 큐의 정렬 기준을 직접 정의해야 한다. 절댓값이 같을 때는 음수를 우선하여 출력해야 한다.

 

[정답]

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

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());
        PriorityQueue<Integer> pq = 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(br.readLine());
            if(request == 0) {
                if(pq.isEmpty())
                    System.out.println("0");
                else
                    System.out.println(pq.poll());
            } else {
                pq.add(request);
            }
        }
    }
}

 

 

여기서 정렬 기준을 새로 정의했는데, 방법은 다음과 같다.

 

두 개의 인자를 비교해 정렬해주며 결과값으로 기준값(o1)보다 비교값(o2)이 더 크면 -1, 기준값과 비교값이 같으면 0, 기준값이 비교값보다 더 크면 1을 리턴해준다.

- o1 < o2 ==> -1
- o1 == o2 ==> 0
- o1 > o2 ==> 1

 

위 코드에서 o1의 절댓값을 first_abs에, o2의 절댓값을 second_abs에 넣었을 때 이 둘의 값이 같다면 음수를 우선 정렬하기 위해 o1과 o2의 실제 크기를 비교하였다. 만약 o1이 더 크다면, 즉 o1이 양수라면 1을 리턴하여 o1의 값이 더 큼을 명시한다. 절댓값이 같지 않다면 first_abs - second_abs를 리턴해 만약 first_abs이 더 크면 양수, 즉 o1이 더 크고 음수라면 second_abs가 더 크므로 o2가 더 크다는 것을 정의한다.

 

객체를 비교할 때도 마찬가지이다. 

 

Comparable

comparable 인터페이스를 상속받아서 클래스의 기본 정렬 기준을 재정의하는 방법이다.

public class Player implements Comparable<Player> {
    // Fields, Getters, Setters 생략

    @Override
    public int compareTo(Player o) {
        return o.getScore() - getScore();
    }
}

public class Main {
    public static void main(String[] args) {
        // Player 객체 여러 개 생성 생략

        Collections.sort(players);
        System.out.println(players); // [Player(name=Chloe, score=1090), Player(name=Eric, score=1018), Player(name=Bob, score=982), Player(name=Dale, score=982), Player(name=Alice, score=899)]
    }
}
출처: https://yuja-kong.tistory.com/174 [유자의 개발 아지트:티스토리]

 

- compareTo의 리턴 결과가 양수

=> compareTo 메서드를 부르는 객체가 더 크고, 파라미터로 들어온 o 객체가 더 작다고 판별

 

- compareTo의 리턴 결과가 0

=> 두 객체의 값이 동일하다고 판별

 

- compareTo의 리턴 결과가 음수

=> compareTo 메서드를 부르는 객체가 더 작고, 파라미터로 들어온 o 객체가 더 크다고 판별

 

위 예시는 내림차순 정렬을 구현한 것이다. 만약 파라미터로 들어온 o 객체의 값이 더 크고 메서드를 부르는 객체의 값이 더 작다고 했을 때 뺀 값은 양수가 되는데, 리턴 값이 양수라면 메서드를 부르는 객체의 값의 우선 순위를 더 높게 두게 된다. 그렇기에 더 작은 값인 메서드 호출 객체의 값이 더 먼저 정렬되게 된다.

 

comparable 인터페이스로 정의한 기준에 따라 정렬하기 위해선 Collection.sort(객체)를 사용하면 된다. 기본 데이터형과 달리 객체의 경우 정렬 기준을 정의하지 않으면 해당 함수 사용시 컴파일 에러가 발생하게 된다.

 

Comparator

클래스 단위가 아닌 객체마다의 정렬 기준을 정의하는 방법이다.

정렬 대상의 클래스를 직접 수정할 수 없거나 정렬 대상 클래스의 정렬 기준이 있고 다른 정렬 기준이 필요한 경우 사용할 수 있다.

Comparator<Player> comparator = new Comparator<Player>() {
    @Override
    public int compare(Player a, Player b) {
        return b.getScore() - a.getScore();
    }
};

Collections.sort(players, comparator);
System.out.println(players); // [Player(name=Chloe, score=1090), Player(name=Eric, score=1018), Player(name=Bob, score=982), Player(name=Dale, score=982), Player(name=Alice, score=899)]
출처: https://yuja-kong.tistory.com/174 [유자의 개발 아지트:티스토리]

 

Comparator 인터페이스의 구현체를 만들고 Collection.sort()나 Array.sort() 메서드의 정렬 인자를 추가로 넘겨주면 된다. 

 

Comparator 객체는 메서드가 하나뿐인 인터페이스를 구현하므로 람다 함수로 대체할 수 있다.

Collections.sort(players, (a, b) -> b.getScore() - a.getScore());
System.out.println(players); // [Player(name=Chloe, score=1090), Player(name=Eric, score=1018), Player(name=Bob, score=982), Player(name=Dale, score=982), Player(name=Alice, score=899)]
출처: https://yuja-kong.tistory.com/174 [유자의 개발 아지트:티스토리]

 

 

 

 

 

 

[참고 자료]

- Do it! 알고리즘 코딩 테스트 자바편

- https://velog.io/@zoo4we/Comparator

Comparator를 이용한 문자열 배열 정렬하기

- https://yuja-kong.tistory.com/174

[Java] 객체 정렬 - Comparable, Comparator