반응형
https://school.programmers.co.kr/learn/courses/30/lessons/43238
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr


풀이
알고리즘 2단계를 간간히 풀다가 3단계를 처음으로 풀어봤습니다.
심사하는데 걸리는 시간이 다른 각 각의 심사관들이 N명을 검사하는데 걸리는 최소 시간을 구하는 문제입니다.
처음에는 1초씩 더 해가면서 풀었더니 시간 초과가 발생해서 이분 탐색을 이용해서 풀었습니다.
1. 심사하는데 걸리는 시간의 최소값(min)과 최대값(max)을 구함
2. 최소값과 최대값의 중간값(mid) [이분 탐색 시간] 을 구함
3. 이분 탐색 시간동안에 심사관들이 몇 명을 처리할 수 있는지(people)를 구함
import java.util.Arrays; class Solution { public long solution(int n, int[] times) { long answer = 0; Arrays.sort(times); // 정렬 long min = 1; // 최소값 long max = (long) times[times.length-1] * n; // 최대값 while (min <= max) { long mid = (min + max) / 2; // 중간값 long person = 0; for (int i=0; i<times.length; i++) { person += mid / (long) times[i]; // 주어진 시간동안 심사할 수 있는 사람 수 } if (person >= n) { // 심사를 받아야할 인원보다 적을 경우 (시간이 부족함) max = mid - 1; answer = mid; } else if (person < n) { // 심사를 받아야할 인원보다 클 경우 (시간이 남음) min = mid + 1; } } return answer; } }
반응형
'알고리즘 > 프로그래머스' 카테고리의 다른 글
[프로그래머스]JAVA - Level2. 124 나라의 숫자 (0) | 2022.07.10 |
---|---|
[프로그래머스]JAVA - Level3. N으로 표현 (0) | 2022.07.09 |
[프로그래머스]JAVA - Level 2. 뉴스 클러스터링 (0) | 2022.06.29 |
[프로그래머스]JAVA - Level 2. 문자열 압축 (0) | 2022.04.17 |
[프로그래머스]JAVA - Level 2. 오픈채팅방 (0) | 2022.04.11 |