강의로 돌아가기
zezeg2

효율성 2번

부분합으로 접근했는데, 효율성 2번만 시간초과가 발생합니다...
도저히 어디가 문제인지 모르겠는데 도와주실 능력자분 계신가요...

작성중인 코드―Solution.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
import java.util.*;
class Solution {
    static int solution(int[] food_times, long k) {
        int answer = 0;
        long maxRotate = Arrays.stream(food_times).max().getAsInt();
        int nof = food_times.length;
        long[] timePerRotate = new long[(int) (maxRotate + 1)];
        timePerRotate[0] = nof;
        for (int i = 0; i < nof; i++) {
            timePerRotate[food_times[i]]--;
            timePerRotate[timePerRotate.length - 1]++;
        }
        for (int i = 1; i < timePerRotate.length; i++) {
            timePerRotate[i] += timePerRotate[i - 1];
        }
        long n = 0;
        long curr = 0;
        long prev = 0;

        for (int i = 0; i < timePerRotate.length; i++) {
            if (i == 0) {
                curr = timePerRotate[1];
            } else {
                timePerRotate[i] += timePerRotate[i - 1];
                curr = timePerRotate[i];
                prev = timePerRotate[i - 1];
            }
            if (k <= curr) {
                n = k == curr ? i + 1 : i;
                break;
            }
        }
        long currTime = k == curr ? curr : prev;
        for (int i = 0; i < nof; i++) {
            if (food_times[i] - (n + 1) < 0) continue;
            currTime++;
            if (currTime > k) {
                answer = i + 1;
                break;
            }
        }
        if (currTime <= k) return -1;
        return answer;
    }
}
0 개의 답변
답변 쓰기
이 입력폼은 마크다운 문법을 지원합니다. 마크다운 가이드 를 참고하세요.