프로그래머스 - 디펜스 게임(Java)

[수정 알림]

파라메트릭 서치 및 우선순위 큐로 문제를 해결했는데, 테케 10번에서 시간초과가 발생하신다는 분이 계셨습니다.

저의 경우 제 방법이 아슬아슬하게 통과를 했던것 같고, 서버 상태에 따라 통과를 못할 수도 있다는 생각을 하게 되었습니다.

 

시간을 조금이라도 더 줄이고자 우선순큐가 아닌 단순 반복으로 문제를 해결했습니다.

우선순위 큐는 O(NlogN) 시간 복잡도가 소요되고, 힙 구조를 유지하는데도 시간에 소요 될 것입니다.

또한, 우선순위 큐 내부에 값을 집어넣는고 빼는 과정에서 박싱과 언박싱이 발생되기 때문에 시간 초과가 날 수 있다고 생각합니다.

아래는 수정한 방법으로 작성했습니다.

 

 

파라메트릭 서치(Parametric Search) 문제입니다.

파라메트릭 서치는 이분 탐색을 통해 주어진 범위의 해답을 결정하는 문제입니다.

 

1. 파라메트릭 서치

이분 탐색을 사용하는 이유는, 특정 범위 내의 탐색을 log(N)으로 끝낼 수 있기 때문입니다.

말로 설명하기에는 너무 어려우니 그림을 통해 설명드리겠습니다.

예제 1번을 그림으로 표현하면 다음과 같습니다.

 

파라메트릭 서치는 그림의 mid의 값을 확인하여 그 범위를 이동시켜야 합니다.

초기 left =0, right = '배열길이'로 할당 합니다.

right가 밖에 있는 이유는, Enemy 배열의 크기는 7이기 때문입니다.

mid는 항상 left와 right의 중간 위치입니다.

 

만약 mid의 위치를 n명의 병사와 k개의 방어권을 통해 막을 수 있다면, left를 mid로 이동시킵니다.

만약 mid의 위치를 n명의 병사와 k개의 방어권을 통해 막을 수 없다면, right를 mid로 이동시킵니다.

 

mid를 막을 수 있다면, mid 보다 작은 위치는 무조건 막을 수 있기 때문에 left 또는 right를 움직여 범위를 줄여나가는 것입니다.

 

현재 mid를 막을 수 있기 때문에, left를 움직여 탐색 범위를 줄입니다.

범위를 줄일 때, left = mid+1을 하여 줄이시면 됩니다.

(이유를 알고 싶으신 분들은 나중에 이진 탐색 상한 및 하한을 검색해보시기 바랍니다.)

또 다시, mid의 위치를 막을 수 있는지 확인합니다.

문제에서는 5라운드 까지만 막을 수 있다고 했습니다.

하지만 현재 mid는 6라운드를 가리키고 있기 때문에, mid의 위치는 막을 수 없습니다.

(0 부터 시작하기 때문입니다.)

 

현재 mid를 막을 수 없으니, right를 움직입니다.

이때는 right = mid를 하시면 됩니다.

범위를 줄였으니 다시 mid를 확인합니다.

현재 mid는 5라운드를 가리키고 있으니 막을 수 있습니다.

즉, left = mid + 1을 하여 범위를 줄입니다.

 

반복 탐색을 하다 보면, left가 right보다 크거나 같아지는 경우가 생깁니다.

이 때, 반복을 종료하시면 됩니다.

 

지금까지 한 탐색은 이진 탐색의 상한 탐색입니다.

즉, left의 위치를 기준으로 막을 수 있는 위치와 없는 위치가 결정됩니다.

left 미만인 범위는 막을 수 있고, left 이상인 범위는 막을 수 없는 위치이게 되는 것입니다.

private static int upperBound() {
    int left = 0;
    int right = enemy.length;

    while (left < right) {
        int mid = (left + right) / 2;

        // mid 위치 막을 수 있는지 확인함
        if (isDefence(mid)) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}

배열은 0 부터 시작하기 때문에, 따로 left의 값을 빼주지 않아도 됩니다.

 

 

2. 막을 수 있는가?

위 코드에 존재하는 isDefence(mid)는 mid의 위치를 막을 수 있는지 없는지 확인하는데 사용합니다.

 

준호가 적절한 시기에 무적권을 사용해야 하기 때문에, 무적권은 최대한 적군의 수가 많을 때 사용해야 합니다.

 

즉, 적군의 수가 적은 라운드 앞으로 이동시켜 병사(n)으로 막고, 적군의 수가 많으면 무적권(k)으로 막아야 합니다.

더 이상 병사들로 막을 수 없을때,

전체 라운드에서 통과한 라운드를 빼 방어권으로 막을 수 있는지 없는지 확인하면 됩니다.

 

(특정 위치인 mid를 n과 k로 막을 수 있는지 확인하기 때문에, 적의 순서를 바꿔도 상관 없습니다.)

private static boolean isDefence(int mid) {
    List<Integer> collect = Arrays.stream(eenemy, 0, mid + 1)
            .boxed()
            .sorted() // 정렬
            .collect(Collectors.toList());
            
    int n = nn;
    
    int size = collect.size();
    
    for (int i = 0; i < size; i++) {
        Integer el = collect.get(i);
        if (el <= n) {
            n -= el;
            continue;
        }
        return kk >= size - i;
    }
    return true;
}

 

 

[구현 코드]

import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

class Solution {
    private static int nn, kk;
    private static int[] eenemy;

    public static int solution(int n, int k, int[] enemy) {
        nn = n;
        kk = k;
        eenemy = enemy;

        return binarySearch();
    }

    private static int binarySearch() {
        int left = 0;
        int right = eenemy.length;

        while (left < right) {
            int mid = (left + right) / 2;

            // mid 위치 까지 막을 수 있는지 확인함
            if (isDefence(mid)) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }

    private static boolean isDefence(int mid) {
        List<Integer> collect = Arrays.stream(eenemy, 0, mid + 1)
                .boxed()
                .sorted()
                .collect(Collectors.toList());

        int n = nn;

        int size = collect.size();

        for (int i = 0; i < size; i++) {
            Integer el = collect.get(i);
            if (el <= n) {
                n -= el;
                continue;
            }
            // 지나간 라운드를 빼서 방어권으로 막을 수 있는지 확인
            return kk >= size - i; 
        }
        return true;
    }
}