SW Expert 15942 JAVA : 외계인 침공

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AYVgWGZKOroDFAQK

SW Expert Academy

 

풀이 예상

만약 지금 내가 K개의 함선을 가지고 있다면,

행성 인구가 K보다 작거나 같은 행성에 침략을 할 수 있는데 침략할 수 있는 행성 중 가장 인구가 많은 행성에 침략과 동원을 해야한다. => 제일 많이 함선을 늘릴 수 있는 방법

 

위 방법으로 풀기 위해 처음에는 그냥 배열에 인구 수를 넣고 정렬한 뒤, 뒤에서부터 탐색하면서 풀었다.

근데 N의 개수가 20만이라서 최악이 20만 x 20만 이라 시간초과가 났다.

 

시간초과를 해결하기 위해 우선순위 큐를 사용했다.

Lpq : K보다 작거나 같은 주민 수 (내림차순 정렬), Hpq : K보다 큰 주민 수 (오름차순 정렬)

 

1. 현재 내가 K개의 함선을 가지고 있다면 Hpq에서 K개와 작거나 같은 값들을 Lpq로 넘긴다.

2. Lpq에서 poll() 한 값이 내가 갈 수 있는 행성 중 가장 인구가 많은 행성이다. 

 

ex) n = 7, k = 8, A[] = {1, 2, 3, 4, 6, 9, 12}

Lpq = {6, 4, 3, 2, 1}

Hpq = {9, 12}

=> Lpq 에서 poll()을 한 6 의 행성을 침략&동원

 

+) total 값을 세 주면서 중간에 끝나면 리턴할 수 있도록 했는데 이 total 값이 int의 값을 넘을 수 있어서 long으로 선언해 줘야 한다.

 

풀이방법 (접근 방법 & 시간복잡도)

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
 
public class Solution {
    static long N,K,answer,total;
    static PriorityQueue<Long> Lqueue;
    static PriorityQueue<Long> Hqueue;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
 
        for (int t = 1; t <= T ; t++) {
            sb.append("#").append(t).append(" ");
            Lqueue = new PriorityQueue<>(Collections.reverseOrder()); //내림차순
            Hqueue = new PriorityQueue<>(); //오름차순
 
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken());
 
            answer = 0;
            total = 0;
 
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) {
                long num = Long.parseLong(st.nextToken());
                total += num;
                if(num <= K) {
                    Lqueue.add(num);
                }else {
                    Hqueue.add(num);
                }
            }
 
            //보유 함선 수 에서 제일 가까운 주민 수(보유함선보다 넘지 않는)의 행성을 먼저 침략하고, 동원한다.
            for (int n = 0; n < N; n++) { //최대 N번 동원
                if(K >= total) { //현재 K가 침량해야 할 주민 수 보다 많거나 같으면 더 이상 동원하지 않아도 된다.
                    sb.append(answer).append("\n");
                    break;
                }
 
                //Hqueue 에서 K보다 작거나 같은거 다 Lqueue로 보냄
                while (true) {
                    if(!Hqueue.isEmpty() && Hqueue.peek() <= K) {
                        Lqueue.add(Hqueue.poll());
                    }else {
                        break;
                    }
                }
 
                //Lqueue 에서 poll한 값을 침공
                if(Lqueue.isEmpty()) {
                    sb.append(-1).append("\n");
                    break;
                }
                long num = Lqueue.poll();
                answer++;
                K += num;
                total -= num;
            }
        }
 
        System.out.println(sb);
 
    }
}

 

결과