[백준] 힙, 해시 테이블 (19638, 1927, 14235, 9375)

자동목차

센티와 마법의 뿅망치(19638)

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken()); // 거인나라 인구 수
        int h = Integer.parseInt(st.nextToken()); // 센티의 키
        int t = Integer.parseInt(st.nextToken()); // 뿅망치 사용가능 횟수

        PriorityQueue<Integer> height = new PriorityQueue<>(Collections.reverseOrder());
        int cnt = 0;

        for (int i = 0; i < n; i++) height.add(Integer.parseInt(br.readLine()));

        while (t-- > 0 && height.peek() >= h) {
            int max = height.poll();

            if (max == 1) { // 거인의 키가 1이면 우선순위 큐의 가장 마지막 요소 일 것이므로 다시 추가하고 반복을 멈춤
                height.add(max);
                break;
            }

            height.add(max / 2);
            cnt++;
        }

        if (height.peek() < h) {
            System.out.println("YES");
            System.out.println(cnt);
        } else {
            System.out.println("NO");
            System.out.println(height.peek());
        }
    }
}

메모리	시간
28216	332

 

최소 힙(1927)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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<>();
        StringBuilder sb = new StringBuilder();

        while (n-- > 0) {
            int x = Integer.parseInt(br.readLine());

            if (x == 0) {
                sb.append(pq.isEmpty() ? 0 : pq.poll()).append("\n");
            } else {
                pq.add(x);
            }
        }
        System.out.println(sb);
    }
}

메모리	시간
26232	280

 

크리스마스 선물(14235)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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<>(Collections.reverseOrder());
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        while (n-- > 0) {
            st = new StringTokenizer(br.readLine());
            int first = Integer.parseInt(st.nextToken());

            if (first == 0) {
                sb.append(pq.isEmpty() ? -1 : pq.poll()).append("\n");
            } else {
                while (st.hasMoreTokens()) {
                    pq.add(Integer.parseInt(st.nextToken()));
                }
            }
        }
        System.out.println(sb);

    }
}

메모리	시간
35584	348

 

패션왕 신해빈(9375)

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine()), n;
        Map<String, Integer> map;
        StringBuilder sb = new StringBuilder();

        while (t-- > 0) {
            n = Integer.parseInt(br.readLine());
            map = new HashMap<>();
            int res = 1;

            while (n-- > 0) {
                String input = br.readLine();
                int idx = input.indexOf(" ");
                String key = input.substring(idx + 1);

                map.put(key, map.getOrDefault(key, 0) + 1);
            }

            for (int val : map.values()) {
                res *= (val + 1);
            }
            sb.append(res - 1).append("\n");
        }
        System.out.println(sb);

    }
}

메모리	시간
14404	96