들어가며

여왕 개미

삼성 SW 역량 테스트 2025년 상반기 오후 2번 문제입니다. 삼성 문제 치곤 간단한 문제였습니다.

문제설명

1차원 수직선으로 표현되는 땅에 여왕 개미와 일 개미들이 개미집을 짓습니다. 좌표는 0 이상 10⁹ 이하의 정수로 한정됩니다. 그리고 다음과 같이 네 개의 명령을 합니다.

마을 건설 : 여왕 개미의 집을 x = 0 위치에 건설. 입력받은 위치들을 이용해 N개의 개미집 건설

개미집 건설 : 새로운 개미집을 p좌표에 건설. 새로운 개미집은 기존 개미집 좌표들보다 큰 값으로 주어짐

개미집 철거 : q번 개미집 하나를 철거. q번 개미집이 이미 철거된 상태거나 아직 지어지지 않은 경우는 주어지지 않음

개미집 정찰 : 정찰을 나갈 개미의 수 r이 주어졌을 때, 모든 개미집의 범위를 커버하면서 정찰에 걸리는 시간을 최소화할 수 있도록 개미를 배치했을 때 걸리는 시간 구하기

※ 1번 명령은 최대 1회, 2, 3번 명령은 최대 10,000회, 4번 명령은 최소 1번, 최대 100회가 주어집니다.

해설

개미집의 위치를 저장할 자료 구조

문제의 조건을 보면 새로운 개미집은 무조건 기존 개미집보다 더 큰 좌표를 가지며, 더 큰 번호를 갖습니다. 또한 개미집의 번호와 위치를 매핑해 저장해야 하므로, 자료구조는 배열 혹은 해시맵을 사용할 수 있습니다. 코드에서는 배열을 사용합니다.

static int[] map = new int[20_001]; // (N 최대 10,000 + 건설 명령 최대 10,000)

1. 마을 건설

마을 건설 명령은 개미집의 개수인 N과 1부터 N까지의 번호로 표현되는 N개의 개미집 위치 xi 가 주어집니다. 따라서 map 자료구조에 그대로 저장하면 됩니다.

2. 개미집 건설

개미집 건설 명령은 새롭게 지어질 개미집의 위치 p 가 주어집니다. map 자료구조에서 지금까지 사용된 개미집 위치 다음 인덱스에 저장합니다.

map[idx++] = p;

3. 개미집 철거

개미집 철거 명령은 철거할 개미집의 번호 q 가 주어집니다. map 에서 해당 인덱스가 제거됐음을 표시해주면 되는데, 저는 거리의 지표로 사용될 수 없는 -1로 저장해 구분했습니다.

map[q] = -1;

4. 개미집 정찰

개미집 정찰 명령은 정찰할 일 개미들의 수 ants 가 주어지고, 일 개미들을 적절하게 배치해 개미집 전체를 정찰할 수 있는 최소 시간을 구해 리턴합니다. 일 개미들은 1초에 1만큼 이동하므로 속력은 1 단위거리/s 가 되고 거리 = 속력 x 시간 에서 단순히 거리 = 시간 이라고 생각할 수 있습니다.

이제 일 개미들을 적절하게 배치해서 최소 거리를 이동시키도록 해야 합니다. 가장 처음 생각할 수 있는 방법은 개미집에 배치할 수 있는 경우의 수를 모두 구하는 완전 탐색입니다. 하지만 시간복잡도가 O(n^r)이므로 시간을 줄일 수 있는 다른 방법을 생각해야 합니다.

그래서 해결책은 이분탐색으로 최소 거리를 찾는 파라매트릭 서치입니다. 개미들의 수 ants 가 고정되어 있고, 개미들은 임의의 시간동안 같은 거리를 이동합니다. 따라서 거리를 이분탐색하면서 mid 동안 r마리의 개미가 이동할 수 있는지 시뮬레이션하면 됩니다.

l = 0; // 개미가 이동하는 가장 작은 거리
r = 1_000_000_000; // 개미가 이동하는 가장 큰 거리

while (l < r) {
    int mid = (l + r) / 2;
    int required = placeAnts(mid);

    if (required > ants) {
        l = mid + 1;
    } else {
        r = mid;
    }
}

return l;

다음과 같이 l(eft), r(ight)를 설정합니다. required 는 각 개미가 mid 거리만큼 커버할 경우 필요한 총 개미의 수입니다. required 를 정찰할 일 개미의 수 ants와 비교했을 때 두 가지로 나눌 수 있습니다.

•

required > ants의 경우 → 더 적은 개미로도 더 넓은 거리 커버 가능하므로 l = mid + 1 

•

required ≤ ants의 경우 → 더 작은 거리로도 가능할 수도 있으므로 r = mid 

코드

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

public class Main {
    static int N;
    static int[] map = new int[20_001]; // (N 최대 10,000 + 건설 명령 최대 10,000)
    static int idx;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int Q = Integer.parseInt(br.readLine());

        for (int i = 0; i < Q; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            int comm = Integer.parseInt(st.nextToken());

            switch (comm) {
                case 100:
                    N = Integer.parseInt(st.nextToken());

                    for (int j = 1; j <= N; j++) {
                        map[j] = Integer.parseInt(st.nextToken());
                    }

                    idx = N + 1;

                    break;
                case 200:
                    int p = Integer.parseInt(st.nextToken());

                    buildHouse(p);
                    break;
                case 300:
                    int q = Integer.parseInt(st.nextToken());
                    breakHouse(q);
                    break;
                case 400:
                    int r = Integer.parseInt(st.nextToken());
                    sb.append(scout(r)).append("\n");
                    break;
            }
        }

        System.out.println(sb);
    }

    private static void buildHouse(int p) {
        map[idx++] = p;
    }

    private static void breakHouse(int q) {
        map[q] = -1; // -1로 삭제된 개미집 구분
    }

    private static int scout(int ants) {
        int l = 0; // 최소 좌표
        int r = 1_000_000_000; // 최대 좌표

        while (l < r) {
            int mid = (l + r) / 2;
            int required = placeAnts(mid);

            if (required > ants) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }

        return l;
    }

    private static int placeAnts(int dist) {
        int cnt = 1;

        int prevIndex = 0;
        int prevX = 0;

        for (int num = 1; num < idx; num++) {
            int x = map[num]; // x 좌표

            if (x == -1) continue; // 이미 삭제된 개미집이라면 건너뛰기

            // 첫번째 개미를 배치하는 로직
            if (prevIndex == 0) {
                prevIndex = num;
                prevX = x;
                continue;
            }

            // 이전 개미가 커버할 수 있는 영역을 초과하면 새로운 개미 배치
            if (x - prevX > dist) {
                prevIndex = num;
                prevX = x;
                cnt++;
            }
        }

        return cnt;
    }
}