삼성 SW 역량 테스트 2025년 상반기 오후 2번 문제입니다. 삼성 문제 치곤 간단한 문제였습니다.
1차원 수직선으로 표현되는 땅에 여왕 개미와 일 개미들이 개미집을 짓습니다. 좌표는 0 이상 10⁹ 이하의 정수로 한정됩니다. 그리고 다음과 같이 네 개의 명령을 합니다.
1.
마을 건설 : 여왕 개미의 집을 x = 0 위치에 건설. 입력받은 위치들을 이용해 N개의 개미집 건설
2.
개미집 건설 : 새로운 개미집을 p좌표에 건설. 새로운 개미집은 기존 개미집 좌표들보다 큰 값으로 주어짐
3.
개미집 철거 : q번 개미집 하나를 철거. q번 개미집이 이미 철거된 상태거나 아직 지어지지 않은 경우는 주어지지 않음
4.
개미집 정찰 : 정찰을 나갈 개미의 수 r이 주어졌을 때, 모든 개미집의 범위를 커버하면서 정찰에 걸리는 시간을 최소화할 수 있도록 개미를 배치했을 때 걸리는 시간 구하기
※ 1번 명령은 최대 1회, 2, 3번 명령은 최대 10,000회, 4번 명령은 최소 1번, 최대 100회가 주어집니다.
문제의 조건을 보면 새로운 개미집은 무조건 기존 개미집보다 더 큰 좌표를 가지며, 더 큰 번호를 갖습니다. 또한 개미집의 번호와 위치를 매핑해 저장해야 하므로, 자료구조는 배열 혹은 해시맵을 사용할 수 있습니다. 코드에서는 배열을 사용합니다.
static int[] map = new int[20_001]; // (N 최대 10,000 + 건설 명령 최대 10,000)마을 건설 명령은 개미집의 개수인 N과 1부터 N까지의 번호로 표현되는 N개의 개미집 위치 xi 가 주어집니다. 따라서 map 자료구조에 그대로 저장하면 됩니다.
개미집 건설 명령은 새롭게 지어질 개미집의 위치 p 가 주어집니다. map 자료구조에서 지금까지 사용된 개미집 위치 다음 인덱스에 저장합니다.
map[idx++] = p;개미집 철거 명령은 철거할 개미집의 번호 q 가 주어집니다. map 에서 해당 인덱스가 제거됐음을 표시해주면 되는데, 저는 거리의 지표로 사용될 수 없는 -1로 저장해 구분했습니다.
map[q] = -1;개미집 정찰 명령은 정찰할 일 개미들의 수 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;
}
}
Loading comments...
