알고리즘/프로그래머스
입국심사 **
베리영young
2024. 1. 30. 21:11
사용 알고리즘: 이분탐색
사용 언어: java
import java.io.*;
import java.util.*;
class Solution {
public long solution(int n, int[] times) {
Arrays.sort(times);
long answer = 0;
//평균 시간에 -> 한 심사대에서 -> 몇 명까지 심사할 수 있냐!!
long left = 1;
long right = times[times.length-1] * (long)n; //최대 이만큼 걸림!
long mid = 0;
while(left <= right) { //배열이 0분~times.length-1분까지인 느낌
//현재 범위에서 최소로 걸리는 시간과 최대로 걸리는 시간의 평균으로 각각 계산해보기
mid = (left+right) /2 ;
System.out.println(right);
long passenger = 0; //평균 시간 내 몇 명이나 심사할 수 있을까
for(int t : times) {
passenger += mid/t;
}
if(passenger < n) { //시간 내에 모든 사람을 심사할 수 없으면, 시간 늘리기
left = mid+1;
}
else { //시간 내에 다 하고도 남는다면, 시간 줄이기
right = mid-1;
answer = mid;
}
}
return left;
}
}
이슈:
1. 최대 걸리는 시간 구하기(right에 해당), times 정렬하기를 제외하고이분탐색으로 이걸 어떻게 풀어야 하는지 감이 오지 않았다. -> 구글링 블로그 참고 후, 걸리는 시간을 일종의 배열처럼 보고 그 안에서 이분탐색을 하면 된다는 걸 깨달음!! (이분탐색이라 하더라도 주어지는 문제가 꼭 배열 형식이 아닐 수 있다!)
풀이 중 이슈:
1. 말도 안 되는 답이 나와서 확인해보니 right에 최대 걸리는 시간을 구해야지~해놓고 time.lenght-1..인덱스 번호만 넣어놨다.. 뭐지?
2. 고쳐도 안 됐는데 left, rigtht, mid의 타입을 int에서 long으로 변환했더니 답 나옴!