https://school.programmers.co.kr/learn/courses/30/lessons/43238
1. 문제 및 접근
들어 오는 수가 너무 말이 안되긴 하다.
각각의 심사관 마다 line안에 집어넣는데 기다리는 순은
어딜 고를거냐 ? 무조건 times가 작은 곳이 아닌(누적x) ,
다 듣는 시간까지 고려 해야하기 때문에 현재 바로 듣는다고 해서 더 빨리 마치는 게 아니네
그럼 고려할 사항이 다 들었을 때 짧은 시간을 계산해야한다
매번 어느 것이 더 빨리 끝날 것인지 찾는
고려 사항이 지금 현재 시간에서 아직 끝나지 않은 것도 몇분 후에 끝나는 지 + 심사관이 걸리는 시간
이걸 근데 마지막 수만 생각하면 안되고, 그 어느 시점에 되면 다 고려해야할 것 같다.
아예 틀렸다 문제는 이진탐색을 원했다. 떠오르질 않는 걸 어떻게 해..
제한사항
- 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.
- 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.
- 심사관은 1명 이상 100,000명 이하입니다.
2. 내 생각
제일 처음에 제한사항을 보고도 떠오르지 않아서 일단 완전탐색으로 진행하려고
매 선택마다, 최선의 선택을 하려고 생각했다.
내 생각의 완탐의 형식은
- 현재 선택 과정에서 (현재 시간에서 다른 심사대가 끝날 시간 + 실제 심사시간)이 가장 작을 경우를 선택
- 사실 10과 7을 고르는 건 현재 시간이 7분이라면 0+7 or 3+10 중 더 적게 걸리는 거
- 같다면 실제 심사시간이 더 적은거 골라라
예를 들어 n= 6, m=2의 예시라면 2^6 = 64라서 간단하지만,
최대 값인 n=1,000,000,000 과 m=100,000 는 ?
100,000^1,00,000,000 = 숫자 아님
숫자가 아니라는데, 꿈도 꾸지말자 ㅠㅠ
3. 풀이
public long solution(int n, int[] times) {
long answer = 0;
//현 시점에서 비어있는 게 아닌, 들어온 time + 기다릴 시간이 젤 less
Arrays.sort(times);
long left = times[0];
long right = times[times.length - 1] * n; // 최악의 경우
while (left <= right) {
long mid = (left + right) / 2;
long sum = 0;
for (int time : times) {
sum = sum + (mid / time);}
if (sum >= n) {
answer = mid;
right = mid - 1;
} else
left = mid + 1;
}
return answer;
}
전체풀이
3-1. 이진탐색
사실 이진 탐색은 O(logN)의 시간복잡도를 가진 아주 빠른 탐색방법이다.
탐색의 범위 자체를 반씩 소거할 수 있는 녀석인데,
쉽게 생각해 up-down 게임이라고 생각하면 접근하기 쉽다.
우리가 1~100의 숫자를 Up인지, Down인지, 최소한의 정답만 외칠 수 있다면,
특정 한 숫자를 부르는 것 보다 50인 반을 골라 up-down을 맞추어 가는 게 베스트
이진탐색의 과정과 중요한 점은
- 오름차순 및 내림차순으로 정렬된 배열이여야 함
- mid 값을 정한 후 반씩 소거하는 과정 반복
- target이 mid 값보다 작으면 mid 기준 왼 쪽 배열을 탐색
- target이 mid 값보다 크다면 mid 기준 오른 쪽 배열 탐색
- 다시 mid 값을 조정 후 반복
대용량의 데이터에서 특정 값을 찾을 때 아주 유용하다.
(사실 생각해보면 내가 아는 빠른 sort의 방식인데 왜 적용을 못했을까..)
3-2. 이진탐색 기초
제일 중요한 정렬된 배열이여야 가능하다..
(보면 Arrays.sort도 DualPivotQuicksort를 쓰는 피벗이 두개긴 하지만 이진탐색의 퀵소트 기반인 것을.. 바보다)
여튼 left 값은 들어온 정렬 값의 최소 값,
right는 최악의 경우 제일 오래 걸리는 심사관이 n명을 모두 심사 했을 때의 경우인
ex)
{7,10}이 걸리는 심사관이 6명을 검사 해야 한다면 60분이 최악일 것이다.
이진 탐색이라면 7과 60의 사이 값 33분으로 먼저 탐색 시작!
3-3 이진탐색 mid
우리가 정한 최소 값과 최대 값이 같거나,
최소 값이 최대 값을 넘어간다면 찾지 못하는 경우이니 탈출조건
우리가 원하는 이진탐색의 활용은 최소와 최대의 반씩 계속 소거하기 위해 mid 값을 (left + right / 2)
sum은 현재 임의로 잡은 mid 만큼의 시간 안에 처리할 수 있는 총 사람의 수를 구해야 한다.
times의 배열을 돌면서
현재 각 심사관마다 처리할 수 있는 사람의 수는 심사관 마다 걸리는 수(time)을 mid로 나눠주고 총 합 sum에 다 더해준다.
위 예시대로라면
time[0]의 심사관은 4.x명 (33/7)
time[1] 의 심사관이라면 3.x명 (33/10)
sum = 7.x
3-4. 이진탐색 배열 크기 재조정
1. 만약에 구한 sum이 n보다 크거나 같다면 ?
우리가 mid를 구한 값 안에 모든 사람이 심사를 받을 수 있다는 뜻이다.
그렇다면 우리가 원하는 건 가능한 최소 시간이기에
답에 answer을 적어주고 다시 탐색할 범위를 mid-1로 정한다면 기존의 값 반으로 줄인 배열이 만들어 질 것이고,
다시 그 반으로 줄여진 배열의 반을 mid값을 정하고 반복 !
ex)
7.x > 6 이기에
다시 배열 조정 후 최적 mid의 값 찾기
2. 만약 구한 sum이 n보다 작다면 ?
현재 우리가 임의로 정한 시간으로는 모든 사람이 심사 받을 수 없다.
즉 mid 값이 부족하니 더 많은 시간을 써야한다는 뜻
더 많은 시간을 써야 하니 mid+1을 다시 시작으로 잡고 다시 그 배열의 mid 값을 지정해줄 것이다.
마지막으로 시작 값이 마지막 값보다 커지면 반복문이 종료되고,
이때 answer에는 모든 사람이 심사받는데 걸리는 최소의 시간인 mid가 저장되어 있을 것이다.
4. 마무리
접근 방법을 애매하게 접근하는 게 문제
애초에 최악과 최선을 기준으로 잡고 단계별로 접근해야 하는데,
중간의 뇌피셜로 접근해서 if문으로 하나씩 줄여가려고 하니까 갈피를 못 잡는 것 같다..
사실 들어온 배열에서만 target을 찾는 형식의 이진탐색만 풀다보니
걸린 시간을 따로 산정해 이진탐색한다는 자체를 귀결시키지 못한 문제 ㅠㅠ
최악의 경우에 걸리는 시간과 최선의 시간에서 중간 값을 정해 탐색의 범위를 줄이는 간단했고, 많이 봤지만
문제 자체를 이진 탐색으로 바로 떠올릴 수 있게 많은 문제를 접근해봐야겠다..
번외로
long 타입 변환을 안해줘서 되게 오래 걸렸다 ^^
앞으로 그냥 실수 없게 long으로 다 해버릴까.. 그렇다면 효율적이지 못한 내가 되겠지 ㅠㅠ
'알고리즘' 카테고리의 다른 글
| 99클럽 코테 스터디 24일차 TIL 가장 먼 노드 (1) | 2024.06.12 |
|---|---|
| 99클럽 코테 스터디 23일차 TIL Capacity To Ship Packages Within D Days (2) | 2024.06.11 |
| 99클럽 코테 스터디 21일차 TIL Count Square Submatrices with All Ones (1) | 2024.06.09 |
| 99클럽 코테 스터디 20일차 TIL Partition Array for Maximum Sum (1) | 2024.06.08 |
| 99클럽 코테 스터디 19일차 TIL Count Sorted Vowel Strings (0) | 2024.06.07 |