https://school.programmers.co.kr/learn/courses/30/lessons/43238#qna
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
틀린 소스코드
import java.util.*;
class Solution {
public long solution(int n, int[] times) {
long answer = 0;
TreeMap<Long, Long> map = new TreeMap<>();
for (int time : times)
map.put((long)time, (long)time);
for (int i = 0; i < n - 1; i++) {
Map.Entry<Long, Long> entry = map.firstEntry();
Long key = entry.getKey();
Long value = entry.getValue();
map.remove(key);
map.put(key + value, value);
}
answer = map.firstEntry().getKey();
return answer;
}
}
틀린 이유
TreeMap을 사용하여 문제를 해결하려 하였다. 하지만 TreeMap은 중복키를 허용하지 않기 때문에 만약 (3, new int []{1,1,1})이 입력으로 들어오는 경우 결과값은 1이 나와야 하지만 3이 나온다. 애초에 n의 수는 최대 1억이기 때문에 for문을 돌리면서 시간초과가 날 것이다.
소스코드
import java.util.*;
class Solution {
long max = 1000000000;
int[] time;
int N;
public long solution(int n, int[] times) {
N = n;
time = times;
long left = 1;
long right = max * max;
while(left<right) {
long mid = (left + right) / 2;
if(possible(mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return right;
}
boolean possible(long mid) {
long n = N;
for (int i : time) {
n -= mid / i;
}
return n <= 0;
}
}
해결방법
이진 탐색을 사용하였다. 10만*log(10억*10억) => 약 600만 이므로 시간초과가 나지 않는다.
'알고리즘 > 프로그래머스' 카테고리의 다른 글
네트워크 (0) | 2023.06.29 |
---|---|
게임 맵 최단거리 (0) | 2023.06.16 |
오픈채팅방 (0) | 2023.06.14 |
디펜스 게임 (0) | 2023.06.14 |
뒤에 있는 큰 수 찾기 (0) | 2023.04.10 |