스택 & 큐 - 자바 백준 카드2: 2164 절댓값 힙: 11286

바로 문제를 풀어봅시다.

백준 2164번 - 카드2

2164번: 카드2

2164번: 카드2

 

 

1. 문제 분석하기

큐를 잘 이해하고 있는지를 묻는 문제입니다. 가장 위의 카드를 가장 아래에 있는 카드 밑으로 옮기는 동작은 큐의 선입선출이 떠오릅니다!

카드의 개수의 최대가 500,000 이므로 시간 복잡도의 제약도 크지 않습니다. 큐로 이 문제를 해결해봅시다.

 

2. 손으로 풀어보기

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

 

 

3. 슈도코드

N (카드의 개수) myQueue (카드의 저장 자료 구조)

for (카드의 개수만큼 반복){
    큐에 카드 저장
}

while(카드가 1장 남을 때까지){
    맨 위의 카드 버림 : poll()
    맨 위의 카드를 가장 아래로 이동: poll(), add()
}

마지막으로 남은 카드 출력

 

4. 코드

public class Main {
    public static void main(String[] args)  {

        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);
        }
        // 카드가 1장 남을 때까지 맨 위 버리고, 맨위 카드를 가장 아래로
        while (myQueue.size() > 1) {
            myQueue.poll();
            myQueue.add(myQueue.poll());
        }

        // 마지막으로 남은 카드 출력
        System.out.println(myQueue.poll());
    }
}

 

백준 11286 절댓값 힙

11286번: 절댓값 힙

11286번: 절댓값 힙

 

1. 문제 분석

N 의 최대 범위가 100,000 이므로 O(nlogn) 시간 복잡도로 문제를 풀어야 합니다.

데이터가 새로 삽입될 때마다 절댓값과 관련된 정렬이 필요하기 때문에 우선순위 큐(Priority Queue)를 사용합시다. 이 때 우선순위 큐의 정렬 기준을 우리가 직접 정의해주어야 합니다. 문제 설명에서 절댓값 힙에 대해 나와있듯이 절댓값이 같을 때는 음수를 우선하여 출력해야 하는 사실도 기억해둡시다.

간단한 Priority Queue 에 대한 소개는 오른쪽 링크에서 보실 수 있습니다. https://sh1mj1-log.tistory.com/123

 

2. 손으로 풀기
3. a. x = 0 일 때

큐가 비어있을 때는 0 출력. 비어있지 않을 때는 절댓값이 최소인 값을 출력합니다. 만약 절댓값이 같다면 음수를 우선하여 출력.

b. x ≠ 0 일 때

add 로 큐에 새로운 값을 추가, 우선순위 큐 정렬 기준으로 자동 정렬합니다.

 

 

3. 슈도 코드

N (질의 요청 개수)

우선순위 큐 선언
- 절대값 기준으로 정렬되도록
- 만약 절대값이 같다면 음수 우선 정렬
for (N 만큼 반복){
    요청이 0일 때 -> 큐가 비어있으면 0, 비어있지 않으면 큐의 front 값 출력 (poll())
    요청이 1일 때 -> 새로운 데이터를 우선순위 큐에 더하기 (add())
}

4. 코드

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> 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(br.readLine());

            if (request == 0) {
                if (MyQueue.isEmpty()) {
                    System.out.println("0");
                } else {
                    System.out.println(MyQueue.poll());
                }
            } else {
                MyQueue.add(request);
            }

        }

    }
}

 

여기서 `MyQueue` 을 선언할 때 `Comparator` 을 사용하여 구현했습니다.

여기서는 `Comparable` 과 `Comparator` 라는 두 인터페이스를 이해해야 합니다. 두 인터페이스로 우리는 “객체를 비교” 할 수 있습니다.

이는 다시 자세히 학습하도록 하고 `Comparator` 의 `compare` 메소드를 사용한 부분만 살펴봅시다.

default initial capacity 로 `PriorityQueue` 을 만듭니다. 이 `PriorityQueue` 의 `elements` 는 특정 `comparator` 에 따라 정렬됩니다.

public PriorityQueue(Comparator<? super E> comparator) {
	this(DEFAULT_INITIAL_CAPACITY, comparator);
}

 

두 arguments 의 순서를 비교합니다. 첫 argument 가 두 번째 argument 보다 작을 때음수, 같을 때 0, 클 때 양수를 리턴합니다.

`signum(compare(x,y)) == -signum(compare(y,z))` 을 항상 만족해야 합니다. (`signum` 함수는 인수가 양수면 +1, 음수면 -1, 0이면 0을 리턴하는 함수)

int compare(T o1, T o2);

 

 

여기까지 살펴보면 어느정도 이해가 될 것입니다. 다시 코드를 봅시다.

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; // 절대값을 기준으로 정렬(절대값이 작은 것이 우선)
      }
  });

 

 

첫번째값과 두번째 값의 절대값이 같다면 `o1`, `o2` 비교해서 `o1` 이 클 때 `comparator` 가 1이라는 것은 낮은 `int` 값이 우선순위가 높도록(최소힙으로) 정렬한다는 의미입니다.

`comparator` 의 리턴값이 양수이면 작은 값이 더 우선순위를 갖는 것입니다. 자바의 `PriorityQueue` 의 기본 정렬이 최소힙 기준이기 때문입니다.

즉, 음수 우선 정렬이 된다는 의미이지요.

 

이 부분이 조금 헷갈릴 수 있습니다. 정리하면

• `PriorityQueue` 는 기본이 최소힙 정렬(작은 값이 큰 우선순위)
• `comparator` 에서 반환값이 양수이다 ↔️ `o1`, `o2` 중 작은 값이 우선
• 위 조건문에서 절대값이 같을 때 `o1 > o2 ? 1 : -1;` ↔️ 음수가 우선

 

이렇게 정리할 수 있겠네요

우선순위 큐를 그냥 선언하여 사용하기는 쉽지만 정렬 기준을 새로 적용하여 선언하는 방법은 꽤 어렵네요.