[랜덤 마라톤] My Cow Ate My Homework(15460)

1. 문제 풀이 아이디어

• 누적 합과 최소값을 배열에 저장하여 문제를 해결할 수 있다.

2. 나의 정답 코드

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bufferedReader.readLine());
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        int[] sum = new int[n + 1];
        int[] score = new int[n + 1];
        int[] min = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            score[i] = Integer.parseInt(stringTokenizer.nextToken());
            sum[i] = sum[i - 1] + score[i];
        }
        int m = score[n];
        min[n - 1] = m;
        for (int i = n - 2; i >= 1; i--) {
            min[i] = Math.min(min[i + 1], score[i + 1]);
        }

        List<Integer> list = new ArrayList<>();
        double max = 0;
        for (int i = 1; i < n - 1; i++) {
            double avg = (double) (sum[n] - sum[i] - min[i]) / (n - i - 1);
            if (avg > max) {
                list.clear();
                list.add(i);
                max = avg;
            } else if (avg == max) {
                list.add(i);
            }
        }
        StringBuilder stringBuilder = new StringBuilder();
        for (int i : list) {
            stringBuilder.append(i).append('\n');
        }
        System.out.print(stringBuilder);
        bufferedReader.close();
    }
}

3. 정리

• 입력 값을 누적 합으로 계산해 sum 배열에 저장한다.

• 점수를 역순으로 순회하며 이전 숫자 중 최소값을 min 배열에 저장한다.

• 문제의 조건에 따라 1부터 n-2까지 순회하며, i부터 n까지의 합에서 최소값을 뺀 평균을 구한다.

• 평균이 max보다 크면 list를 비우고 현재 인덱스를 추가한 뒤, max 값을 갱신한다.

• 평균이 max와 같다면, 현재 인덱스를 list에 추가한다.

• 마지막으로 list의 값을 출력하여 문제를 해결한다.