디스크 컨트롤러
문1) 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다.
예를들어
- 0ms 시점에 3ms가 소요되는 A작업 요청
- 1ms 시점에 9ms가 소요되는 B작업 요청
- 2ms 시점에 6ms가 소요되는 C작업 요청와 같은 요청이 들어왔습니다. 이를 그림으로 표현하면 아래와 같습니다.
한 번에 하나의 요청만을 수행할 수 있기 때문에 각각의 작업을 요청받은 순서대로 처리하면 다음과 같이 처리 됩니다.
- A: 3ms 시점에 작업 완료 (요청에서 종료까지 : 3ms)
- B: 1ms부터 대기하다가, 3ms 시점에 작업을 시작해서 12ms 시점에 작업 완료(요청에서 종료까지 : 11ms)
- C: 2ms부터 대기하다가, 12ms 시점에 작업을 시작해서 18ms 시점에 작업 완료(요청에서 종료까지 : 16ms)이 때 각 작업의 요청부터 종료까지 걸린 시간의 평균은 10ms(= (3 + 11 + 16) / 3)가 됩니다.
하지만 A → C → B 순서대로 처리하면
- A: 3ms 시점에 작업 완료(요청에서 종료까지 : 3ms)
- C: 2ms부터 대기하다가, 3ms 시점에 작업을 시작해서 9ms 시점에 작업 완료(요청에서 종료까지 : 7ms)
- B: 1ms부터 대기하다가, 9ms 시점에 작업을 시작해서 18ms 시점에 작업 완료(요청에서 종료까지 : 17ms)이렇게 A → C → B의 순서로 처리하면 각 작업의 요청부터 종료까지 걸린 시간의 평균은 9ms(= (3 + 7 + 17) / 3)가 됩니다.
각 작업에 대해 [작업이 요청되는 시점, 작업의 소요시간]을 담은 2차원 배열 jobs가 매개변수로 주어질 때, 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리하면 평균이 얼마가 되는지 return 하도록 solution 함수를 작성해주세요. (단, 소수점 이하의 수는 버립니다)
제한사항
- jobs의 길이는 1 이상 500 이하입니다.
- jobs의 각 행은 하나의 작업에 대한 [작업이 요청되는 시점, 작업의 소요시간] 입니다.
- 각 작업에 대해 작업이 요청되는 시간은 0 이상 1,000 이하입니다.
- 각 작업에 대해 작업의 소요시간은 1 이상 1,000 이하입니다.
- 하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다.
입출력 예
| jobs | return |
|---|---|
[[0, 3], [1, 9], [2, 6]] | 9 |
입출력 예 설명
문제에 주어진 예와 같습니다.
- 0ms 시점에 3ms 걸리는 작업 요청이 들어옵니다.
- 1ms 시점에 9ms 걸리는 작업 요청이 들어옵니다.
- 2ms 시점에 6ms 걸리는 작업 요청이 들어옵니다.
나의 풀이
처음 구현한 로직 (실패)
package programmers;
import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;
public class DiskController {
static class Job {
int request;
int period;
public Job(int request, int period) {
this.request = request;
this.period = period;
}
}
public static int solution(int[][] jobs) {
Arrays.sort(jobs, Comparator.comparingInt(k -> k[1]));
Queue<Job> q = new LinkedList<>();
for(int[] job : jobs) {
q.add(new Job(job[0], job[1]));
}
int wait = 0;
int task = 0;
double sum = 0.0;
while(!q.isEmpty()) {
Job job = q.poll();
task = wait + job.period + job.request;
wait = task - job.request;
sum += wait - job.request;
}
int average = (int)sum / jobs.length;
System.out.println(average);
return average;
}
public static void main(String[] args) {
int[][] jobs = {{0, 3}, {1, 9}, {2, 6}};
solution(jobs);
}
}Priority Queue를 사용한 로직
package programmers;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
public class DiskController {
static class Job {
int request;
int period;
public Job(int request, int period) {
this.request = request;
this.period = period;
}
}
public static int solution(int[][] jobs) {
Arrays.sort(jobs, Comparator.comparingInt(o -> o[0]));
PriorityQueue<Job> pq = new PriorityQueue<>(Comparator.comparingInt(o -> o.period));
int time = 0;
int sum = 0;
int jobsIndex = 0;
int count = 0;
while (count < jobs.length) {
while (jobsIndex < jobs.length && jobs[jobsIndex][0] <= time) {
pq.add(new Job(jobs[jobsIndex][0], jobs[jobsIndex][1]));
jobsIndex++;
}
if (!pq.isEmpty()) {
Job job = pq.poll();
time += job.period;
sum += time - job.request;
count++;
} else {
time = jobs[jobsIndex][0];
}
}
return sum / jobs.length;
}
public static void main(String[] args) {
int[][] jobs = {{0, 3}, {1, 9}, {2, 6}};
solution(jobs);
}
}
나의 구현
처음 구현한 로직에서 생각하지 못했던 부분
- 나는 작업 처리 시간만을 고려하여 가장 짧은 작업을 먼저 처리할려고 함
👉🏻 이 접근법은 작업의 실제 도착 순서를 무시하기 때문에, 특정 작업이 불필요하게 오랫동안 대기할 수 있음
Before
After
- 일반 큐(Queue) 사용 → 우선순위 큐(PriorityQueue) 사용
내가 잘못생각했던 점은 먼저, 작업 처리시간을 정렬한 뒤, Queue에 이를 넣기때문에, 굳이 PriorityQueue를 쓰지않아도 괜찮겠다고 생각함
👉🏻 일반 큐를 사용하면 정렬의 한계가 존재하는데, 큐에 요소를 추가하기 전에 정렬을 수행해야 하며, 이 정렬은 큐에 추가된 후에는 변경할 수 없음. 따라서 동적인 상황, 즉 새로운 작업이 추가되는 상황에서 최적의 순서를 유지하기가 어려움
우선순위 큐(PriorityQueue)의 이점
1. 효율적인 최소값 접근 :
- 즉각적인 최소값 접근 : 최소 힙(Min - Heap)의 루트는 항상 힙에 있는 가장 작은 요소
이를 통해 우선순위가 가장 높은(여기서는 처리 시간이 가장 짧은) 작업에 대한
즉각적인 접근이 가능함
- 데이터 스트림 처리 : 실시간 데이터 스트림이나 동적으로 변화하는
데이터 세트에서 최소값을 효율적으로 관리할 수 있음
최소 힙(min-heap) 구조 : 최소 힙은 완전 이진 트리의 일종으로, 각 노드가 자식 노드보다
작거나 같은 값을 가지는 특성을 가짐 (우선순위 큐는 최소 힙 구조로 구현됨)
2. 시간 복잡도 이점 :
- 데이터 추가/삭제의 효율성 : 최소 힙에서의 데이터 추가('offer','add')나
삭제('poll','remove')작업은 O(log n)시간 복잡도를 가짐
- 대규모 데이터 세트 처리 : 큰 데이터 세트에서도 빠르게 작업을 추가하고 제거할 수 있어
우선순우에 따른 동적 스케줄링에서 효과적임
3. 데이터 구조의 유연성 :
- 동적 크기 조정 : 최소 힙은 배열 기반의 구현을 통해 크기 조정이 가능함
이는 고정된 크기의 배열이나 다른 정적 데이터 구조와 비교했을 때, 유연성을 제공
- 다양한 요소 처리 : 다양한 타입의 요소들을 우선순위에 따라 관리할 수있음
사용자 정의 객체에서도 비교자(Comparator)를 통해 우선순위를 결정할 수 있음| 잘못된 while문 구현 | 수정된 while문 구현 |
|---|---|
 |  |
수정된 로직의 전체적인 흐름을 보자
jobs = {{0,3},{1,9},{2,6}}을 가지고 작업 스케줄링이
어떻게 이루어지는지 단계별로 보자
1. 작업 요청 시간 기준 정렬
- Arrays.sort(jobs, Comparator.comparingInt(o -> o[0]);
- 주어진 작업 jobs는 요청시간(request)을 기준으로 오름차순 정렬
- 정렬된 결과 : {{0,3},{1,9},{2,6}} (원래 배열과 동일)
2. 우선순위 큐 초기화
- PriorityQueue<Job> pq = new PriorityQueue<>(Comparator.comparingInt(o -> o.period));
- 처리 시간(period)을 기준으로 하는 최소 힙(min-heap) 우선순위 큐 생성
3. 작업 스케줄링 로직
- 초기 변수 : time, sum, jobIndex, count = 0;
- while 루프는 count < jobs.length 일 동안 실행
4. 작업 스케줄링 단계별 동작
- 첫 번째 루프(time = 0)
- 첫 번째 작업 {0,3}이 큐에 추가
- 우선순위 큐 상태 : (0,3)
- pq.poll()로 큐에서 (0,3)을 꺼내고 time +=3, sum +=3, count++
- 현재 time = 3, sum = 3, count = 1
- 두 번째 루프(time = 3)
- jobsIndex = 1과 2인 작업 {1,9},{2,6}이 조건을 만족하므로 큐에 추가
- 우선순위 큐 상태 : (2,6),(1,9) (처리 시간 기준 정렬)
- pq.poll()로 큐에서 (2,6)을 꺼내고 time +=6, sum +=7, count++
- 현재 time = 9, sum = 10, count = 2
- 세 번째 루프(time = 9)
- 우선순우 큐에는 (1,9)만 남아 있음
- pq.poll()로 큐에서 (1,9)를 꺼내고, time += 9, sum +=17, count++
- 현재 time = 18, sum = 27, count = 3
5. 평균 대기 시간 계산
- return sum / jobs.length;
- 평균 대기 시간 : 27 / 3 = 9입국심사
문2) n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.
처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.
모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.
입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.
제한사항
- 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.
- 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.
- 심사관은 1명 이상 100,000명 이하입니다.
입출력 예
| n | times | return |
|---|---|---|
| 6 | [7,10] | 28 |
입출력 예 설명
- 가장 첫 두 사람은 바로 심사를 받으러 갑니다.
- 7분이 되었을 때, 첫 번째 심사대가 비고 3번째 사람이 심사를 받습니다.
- 10분이 되었을 때, 두 번째 심사대가 비고 4번째 사람이 심사를 받습니다.
- 14분이 되었을 때, 첫 번째 심사대가 비고 5번째 사람이 심사를 받습니다.
- 20분이 되었을 때, 두 번째 심사대가 비지만 6번째 사람이 그곳에서 심사를 받지 않고 1분을 더 기다린 후에 첫 번째 심사대에서 심사를 받으면 28분에 모든 사람의 심사가 끝납니다.
나의 풀이
package programmers;
public class ImmigrationScreening {
public static long getMax(int[] times) {
long max = 0;
for(int time : times) {
if(time > max) {
max = time;
}
}
return max;
}
public static long solution(int n, int[] times) {
long left = 1;
long right = (long)n * getMax(times);
long answer = right;
while(left <= right) {
long mid = (left + right) / 2;
long sum = 0;
for(int time : times) {
sum += mid / time;
}
if(sum >= n) {
answer = Math.min(answer, mid);
right = mid - 1;
}else {
left = mid + 1;
}
}
return answer;
}
public static void main(String[] args) {
int n = 6;
int[] times = {7,10};
solution(n, times);
}
}
나의 생각
이진 탐색 알고리즘이라는 개념에 대해 알고는 있었으나, 이진 탐색 알고리즘을 적용해본 첫 번째 문제였다.
먼저, 주어진 매개변수를 먼저 살펴보면, n = 입국 심사를 기다리는 사람의 수, times배열에는 각 심사관이 한명을 심사하는데 걸리는 시간을 나타낸다.
즉, times.length = 심사관의 수가 된다. 따라서, 심사관이 2명이며 심사 당 각 각 7분,10분이 소요되며 총인원은 6명이다.
다음으로 solution()에 존재하는 지역변수 left, right, answer을 보면 left는 심사관이 한명을 심사하는데 걸리는 최소의 시간을 의미하며, 0분은 말이 되지않으므로, 1분으로 잡는다. 그리고 right는 심사관이 모든 인원을 심사하는데 걸리는 최대의 시간을 의미하며 getMax() 메서드를 호출한다.
동작을 보면 getMax() 메서드는 매개변수 int[] times에서 제일 큰 값을 검출하여 리턴한다. 따라서 위 로직의 예로보면 n(6), getMax(times)(10) 이기때문에 6 * 10 = 60이 된다.
핵심 로직은 다음과 같다.
- 입력을 바탕으로 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 얻는 과정을 보자.
left = 1, right = 60
1. mid = (1 + 60) / 2 = 30
sum = (30 / 7) + (30 / 10 ) → (7 >= 6)
answer = 30
right = 29
2. mid = (1 + 30) / 2 = 15
sum = (15 / 7) + (15 / 10 ) → (3 < 6)
left = 16
3. mid = (16 + 29) / 2 = 22
sum = (22 / 7) + (22 / 10 ) → (5 < 6)
left = 23
4. mid = (23 + 29) / 2 = 26
sum = (26 / 7) + (26 / 10) → (5 < 6)
left = 27
5. mid = (27 + 29) / 2 = 28
sum = (28 / 7) + (28 / 10) → (6 >= 6)
answer = 28
right = 27
6. mid = (27 + 27) / 2 = 27
sum = (27 / 7) + (27 / 10) → (5 < 6)
left = 28
7. left > right
answer = 28
가장 긴 팰린드롬
문3) 앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다.
문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return하는 solution 함수를 완성해 주세요.
예를들면, 문자열 s가 "abcdcba"이면 7을 return하고 "abacde"이면 3을 return합니다.
제한사항
- 문자열 s의 길이 : 2,500 이하의 자연수
- 문자열 s는 알파벳 소문자로만 구성
입출력 예
| s | answer |
|---|---|
| "abcdcba" | 7 |
| "abacde" | 3 |
입출력 예 설명
입출력 예 #1
- 4번째자리 'd'를 기준으로 문자열 s 전체가 팰린드롬이 되므로 7을 return합니다.
입출력 예 #2
- 2번째자리 'b'를 기준으로 "aba"가 팰린드롬이 되므로 3을 return합니다.
나의 풀이
package programmers;
public class Palindrome {
public static int expand(String s, int left, int right) {
while(left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
return right - left - 1;
}
public static int solution(String s) {
if (s.length() == 1) return 1;
int start = 0, end = 0;
for(int i = 0; i < s.length(); i++) {
int oddLength = expand(s, i, i);
int evenLength = expand(s,i, i+1);
int len = Math.max(oddLength, evenLength);
if(len > end - start) {
start = i - (len - 1) / 2;
end = i + len / 2;
}
}
return end - start + 1;
}
public static void main(String[] args) {
solution("abacde");
}
}
나의 생각
팰린드롬을 보면 문자에 따라 홀수 팰리드롬이 있을수 있고, 짝수 팰리드롬이 존재할 수도 있다. 따라서, 팰린드롬이 홀수개의 문자로 이루어져있는지, 짝수개의 문자로 이루어져있는지 확인해야한다.
-
홀수 : 하나의 문자(i)를 중심으로 양쪽으로 확장하여 홀수 길이의 팰린드롬을 찾음. 예:
aba에서b가 중심 -
짝수 : 두 문자사이(i와 i+1)를 중심으로 양쪽으로 확장하여 짝수 길이의 팰린드롬을 찾음. 예 :
abba에서b와b사이가 중심
팰린드롬은 홀수, 짝수 상관없이 한개의 문자만 같을수도, 두개의 문자만 같을수도, 전체가 같을 수도 있다. 따라서, 중심을 기준으로 하여 왼쪽, 오른쪽 한 칸씩 shift하는 방식을 채택
left와right확장left--와right++는 중심점에서 시작하여 양쪽으로 팰린드롬이 확장되는 것을 나타냄. 즉, 양쪽 문자가 같으면 계속 확장함
return right - left - 1인 이유?- 팰린드롬의 실제 길이를 계산함. while 루프에서 마지막으로
left--와right++가 실행된 후, 실제 팰린드롬 범위를 벗어난 상태. 따라서,right - left - 1을 하여 벗어난 범위에서 정상범주로 맞추어 정확한 길이를 반환
- 팰린드롬의 실제 길이를 계산함. while 루프에서 마지막으로
이렇게 구한
oddLength,evenLength를 구하여 둘 중 길이가 더 긴 길이를 len 변수에 넣음
- 현재의 로직에서
start와end의 계산은 현재 중심점(i)에서 확장된 팰린드롬의 경계를 찾는데 사용되며, 이 계산은 팰린드롬의 길이(len)와 중심점(i)을 기반으로 하며, 홀수 길이와 짝수 길이 팰린드롬 모두를 처리할 수 있도록 설계되어있음
홀수 길이 팰린드롬
홀수 길이 팰린드롬의 경우, 중심점은 팰린드롬의 정중앙에 위치함
예를들어, `aba`에서 `b`가 중심점임
1. start 계산
- 팰린드롬의 길이가 홀수일 때, (len - 1) / 2는 중심점에서 시작점까지의 거리
i - (len - 1) / 2 계산으로 팰린드롬의 시작점을 찾음
2. end 계산
- i + len / 2 계산으로 팰린드롬의 끝점을 찾음
여기서 len / 2는 중심점에서 끝점까지의 거리
짝수 길이 팰린드롬
짝수 길이 팰린드롬의 경우, 두 중심점 사에 있는 문자들이 팰린드롬을 형성함
예를들어, `abbad에서 `b`와`b`가 중심점임
1. start 계산과 end 계산은 홀수 길이 팰린드롬과 동일return end - start + 1을 하는 이유는 ?
- 팰린드롬의 길이를 정확하게 계산하기 위함
- 여기서
start,end는 각각 팰린드롬의 시작 인덱스와 끝 인덱스를 나타냄
인덱스는 0부터 시작하기 때문에, 길이를 계산할 때는 시작 인덱스와 끝 인덱스 사이의 거리에 1을 더해야 정확한 길이가 됨
예를들어, 문자열 "abba"에서 팰린드롬 "abba"의 start = 0이고 end = 3이다.
여기서 end - start는 3 - 0 = 3이지만, 실제 글자 수보다 1이 작음
따라서, 팰린드롬의 길이는 4이므로, 정확한 길이를 얻기 위해 end - start +1이 필요함참고
브루트 포스(Brute Force) 방식
package programmers;
public class Palindrome {
public static boolean isPalindrome(String s, int start, int end) {
while(start < end) {
if(s.charAt(start) != s.charAt(end)){
return false;
}
start++;
end--;
}
return true;
}
public static int solution(String s) {
int maxLength = 0;
for(int start = 0; start < s.length(); start++) {
for(int end = s.length() - 1; end >= start; end--) {
if(s.charAt(start) == s.charAt(end) && isPalindrome(s, start, end)) {
maxLength = Math.max(maxLength, end - start + 1);
}
}
}
return maxLength;
}
public static void main(String[] args) {
solution("abacde");
}
}
동적 프로그래밍(Dynamic Programming) 방식
package programmers;
import java.util.Arrays;
public class Palindrome {
public static int solution(String s) {
int n = s.length();
boolean[][] dp = new boolean[n][n];
int maxLength = 1;
// 한 글자는 모두 팰린드롬
for(int i = 0; i < n; i++) {
dp[i][i] = true;
}
// 두 글자 팰린드롬
for(int i = 0; i < n - 1; i++) {
if(s.charAt(i) == s.charAt(i+1)) {
dp[i][i + 1] = true;
maxLength = 2;
}
}
// 길이가 3 이상인 팰린드롬 확인
for(int len = 3; len <= n; len++) {
for(int start = 0; start <= n - len; start++) {
int end = start + len - 1;
if (s.charAt(start) == s.charAt(end) && dp[start + 1][end - 1]) {
dp[start][end] = true;
maxLength = len;
}
}
}
return maxLength;
}
public static void main(String[] args) {
solution("abbacde");
}
}
숫자 게임
문4) xx 회사의 2xN명의 사원들은 N명씩 두 팀으로 나눠 숫자 게임을 하려고 합니다. 두 개의 팀을 각각 A팀과 B팀이라고 하겠습니다. 숫자 게임의 규칙은 다음과 같습니다.
- 먼저 모든 사원이 무작위로 자연수를 하나씩 부여받습니다.
- 각 사원은 딱 한 번씩 경기를 합니다.
- 각 경기당 A팀에서 한 사원이, B팀에서 한 사원이 나와 서로의 수를 공개합니다. 그때 숫자가 큰 쪽이 승리하게 되고, 승리한 사원이 속한 팀은 승점을 1점 얻게 됩니다.
- 만약 숫자가 같다면 누구도 승점을 얻지 않습니다.
전체 사원들은 우선 무작위로 자연수를 하나씩 부여받았습니다. 그다음 A팀은 빠르게 출전순서를 정했고 자신들의 출전 순서를 B팀에게 공개해버렸습니다. B팀은 그것을 보고 자신들의 최종 승점을 가장 높이는 방법으로 팀원들의 출전 순서를 정했습니다. 이때의 B팀이 얻는 승점을 구해주세요.
A 팀원들이 부여받은 수가 출전 순서대로 나열되어있는 배열 A와 i번째 원소가 B팀의 i번 팀원이 부여받은 수를 의미하는 배열 B가 주어질 때, B 팀원들이 얻을 수 있는 최대 승점을 return 하도록 solution 함수를 완성해주세요.
제한사항
A와B의 길이는 같습니다.A와B의 길이는1이상100,000이하입니다.A와B의 각 원소는1이상1,000,000,000이하의 자연수입니다.
입출력 예
| A | B | result |
|---|---|---|
[5,1,3,7] | [2,2,6,8] | 3 |
[2,2,2,2] | [1,1,1,1] | 0 |
입출력 예 설명
입출력 예 #1
- A 팀은 숫자 5를 부여받은 팀원이 첫번째로 출전하고, 이어서 1,3,7을 부여받은 팀원들이 차례대로 출전합니다.
B 팀원들을 4번, 2번, 3번, 1번의 순서대로 출전시킬 경우 팀원들이 부여받은 숫자들은 차례대로 8,2,6,2가 됩니다. 그러면, 첫 번째, 두 번째, 세 번째 경기에서 승리하여 3점을 얻게 되고, 이때가 최대의 승점입니다.
입출력 예 #2
- B 팀원들을 어떤 순서로 출전시켜도 B팀의 승점은 0점입니다.
나의 풀이
package programmers;
import java.util.Arrays;
public class NumbersGame {
public static int solution(int[] A, int[] B) {
int answer = 0;
Arrays.sort(A);
Arrays.sort(B);
int i = A.length - 1;
int j = B.length - 1;
while (i >= 0 && j >= 0) {
if (B[j] > A[i]) {
answer++;
j--;
}
i--;
}
return answer;
}
public static void main(String[] args) {
int[] A = {5,1,3,7};
int[] B = {2,2,6,8};
solution(A, B);
}
}
기지국 설치
문5) N개의 아파트가 일렬로 쭉 늘어서 있습니다. 이 중에서 일부 아파트 옥상에는 4g 기지국이 설치되어 있습니다. 기술이 발전해 5g 수요가 높아져 4g 기지국을 5g 기지국으로 바꾸려 합니다. 그런데 5g 기지국은 4g 기지국보다 전달 범위가 좁아, 4g 기지국을 5g 기지국으로 바꾸면 어떤 아파트에는 전파가 도달하지 않습니다.
예를 들어 11개의 아파트가 쭉 늘어서 있고, [4, 11] 번째 아파트 옥상에는 4g 기지국이 설치되어 있습니다. 만약 이 4g 기지국이 전파 도달 거리가 1인 5g 기지국으로 바뀔 경우 모든 아파트에 전파를 전달할 수 없습니다. (전파의 도달 거리가 W일 땐, 기지국이 설치된 아파트를 기준으로 전파를 양쪽으로 W만큼 전달할 수 있습니다.)
- 초기에, 1, 2, 6, 7, 8, 9번째 아파트에는 전파가 전달되지 않습니다.
- 1, 7, 9번째 아파트 옥상에 기지국을 설치할 경우, 모든 아파트에 전파를 전달할 수 있습니다.
- 더 많은 아파트 옥상에 기지국을 설치하면 모든 아파트에 전파를 전달할 수 있습니다.
이때, 우리는 5g 기지국을 최소로 설치하면서 모든 아파트에 전파를 전달하려고 합니다. 위의 예시에선 최소 3개의 아파트 옥상에 기지국을 설치해야 모든 아파트에 전파를 전달할 수 있습니다.
아파트의 개수 N, 현재 기지국이 설치된 아파트의 번호가 담긴 1차원 배열 stations, 전파의 도달 거리 W가 매개변수로 주어질 때, 모든 아파트에 전파를 전달하기 위해 증설해야 할 기지국 개수의 최솟값을 리턴하는 solution 함수를 완성해주세요
제한사항
- N: 200,000,000 이하의 자연수
- stations의 크기: 10,000 이하의 자연수
- stations는 오름차순으로 정렬되어 있고, 배열에 담긴 수는 N보다 같거나 작은 자연수입니다.
- W: 10,000 이하의 자연수
입출력 예
| N | station | W | anwer |
|---|---|---|---|
| 11 | [4,1] | 1 | 3 |
| 16 | [9] | 2 | 3 |
입출력 예 설명
입출력 예 #2
- 초기에, 1~6, 12~16번째 아파트에는 전파가 전달되지 않습니다.
- 3, 6, 14번째 아파트 옥상에 기지국을 설치할 경우 모든 아파트에 전파를 전달할 수 있습니다.
나의 풀이
package programmers;
public class BaseStationConstruction {
public static int solution(int n, int[] stations, int w) {
int range =(2 * w) + 1;
int start = 1;
int cnt = 0;
for(int station : stations) {
int lowerBound = Math.max(station - w, 1);
int upperBound = Math.min(station + w, n);
if(start < lowerBound) {
int unconvered = lowerBound - start;
cnt += (unconvered + range - 1) / range;
}
start = upperBound + 1;
}
if (start <= n) {
cnt += (n - start + range) / range;
}
System.out.println(cnt);
return cnt;
}
public static void main(String[] args) {
int[] stations = {9};
solution(16, stations, 2);
}
}
나의 생각
