2022 03 18

2022-03-18¶

PriorityQueue 활용하여 문제 풀기¶

문제 : https://www.acmicpc.net/problem/1202
나의 방법
1. 보석 가격 내림차순으로 정렬 (비싼 -> 싼)
2. 가방 무게 오름차순으로 정렬 (가벼운 -> 무거운)
3. 보석 for문 돌면서, 보석이 들어갈 가방 중 가장 가벼운데에 넣기
  - 이때 이분 탐색을 쓰면서 logn으로 탐색하도록 함

해당 방식이 시간 초과가 난 이유
- 정렬 O(NlogN)
- 넣을 수 있는 가방 이분 탐색 O(logN) * 보석 갯수 O(M)
- 보석 For문 돌면서 매번 이분탐색 <= 병목!

PriorityQueue 사용
1. 보석 무게 오름차순으로 정렬 (가벼운 -> 무거운)
2. 가방 무게 오름차순으로 정렬 (가벼운 -> 무거운)
3. 가방 for문 돌면서...
  - 보석 while문 돌자!
  - 현재 가방 무게 >= 보석 무게 의 경우, 가방에 담을 수 있다는 뜻이니!
  - PriorityQueue를 만들어 보석의 가격만 담아두자!
  - 보석 while문이 끝나면, PQ에서 poll 해서 가장 비싼 가격을 더하자 (해당 가방으로 담을 수 있는 가장 비싼 보석의 가격)
  - 이미 더 가벼운 무게의 보석들은 PQ에 담았으니, 나머지 for문 진행 착착!

PQ 방식 시간 복잡도 계산
- 정렬 O(NlogN)
- For문을 한번에 돌면서 O(보석 수 + 가방 수) 를 통해서 해결 할 수 있음
  - PQ를 씀으로써 기존의 O(MlogN) 을 O(M + N)으로 단축!

import java.util.*;

class Main {  

    public static List<Treasure> treasures = new ArrayList<>();
    public static List<Integer> bags = new ArrayList<>();
    public static int bagSize;

    public static void main(String args[]) { 
        Scanner in = new Scanner(System.in);
        int treasureNumber = in.nextInt();
        int bagNumber = in.nextInt();
        for(int i=0; i<treasureNumber; i++) {
            int weight = in.nextInt();
            int price = in.nextInt();
            treasures.add(new Treasure(weight, price));
        }
        for(int i=0; i<bagNumber; i++) {
            bags.add(in.nextInt());
        }

        Collections.sort(treasures);
        Collections.sort(bags);

        long answer = 0;
        Queue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());
        int j=0; 
        for(int i=0; i<bagNumber; i++) {
            int currentBag = bags.get(i);

            while(j < treasureNumber && treasures.get(j).weight <= currentBag) {
                queue.add(treasures.get(j).price);
                j++;
            }

            if (!queue.isEmpty())
            {
                answer+=queue.poll();
            }
        }

        System.out.println(answer);
    }
}

class Treasure implements Comparable<Treasure>
{
    int weight; 
    int price;

    Treasure(int weight, int price) {
        this.weight = weight;
        this.price = price;
    }

    @Override
    public int compareTo(Treasure o) {
        return this.weight - o.weight;
    }
}

재귀와 하노이의 탑¶

문제: https://brenden.tistory.com/31
하노이의 탑
- n개의 원판을 A -> C로 이동하는 경우의 수 1. 작은 원판 n-1 개를 A -> B 이동 2. 큰 원판 1개 A -> C 이동 3. 작은 원판 n-1 개를 B -> C 이동
- "원반 n개를 이동하는 문제는 원반 n-1개로 이동하는 문제로 세분화되고, 결국 원반 1개를 이동하는 문제로 세분화 된다고 보면 됩니다"

코드

// from에 꽂힌 num개의 원반을 by를 거쳐 to로 이동
public static void moveHanoiTower(int num, int from, int by, int to) {
    if (num == 1) {
        System.out.println("원반" + num + "을 " + from + "에서 " + to + "로 이동");    
    } else {
        // STEP1. num-1 개 A에서 B로 이동 (C를 거쳐서)
        moveHanoiTower(num - 1, from, to, by)
        // STEP2. 가장 큰 원판 A -> C
        System.out.println("원반" + num + "을 " + from + "에서 " + to + "로 이동");
        // STEP3. num-1 개 B에서 C로 이동 (A를 거쳐서)
        moveHanoiTower(num-1, by, from, to);
    }
}