알고리즘 문제 해결 전략_FESTIVAL

도입

구종만 저자의 알고리즘 문제 해결 전략 책의 첫번째 문제.

예전에 한참 아무것도 모르고 백준에서 들입다 문제만 풀다가 알고리즘에 대해서 제대로 공부해보고자 샀던 책인데, 1권 절반정도 읽다가 덮은채로 몇년이 지났던 것 같다.

중간에 그만두었던 이유는 다음과 같다.

1. 책 해설이 CPP로 되어있어 JAVA가 메인인 나에게는 다소 불친절했다.
2. 문제 원본 링크를 못찾았다... 지금 생각해보면 구글에 검색 제대로 안해보는 초보개발자...한심쓰..
3. 원본 링크를 못찾으니 이걸 풀어도 기껏 책에 나와있는 예제 입력이나 통과하지, 진짜로 통과하는지를 알 길이 없으니 흥미 저하..
4. 실무에서 어떻게 쓰일 수 있나 하는 의구심 + 실무에서 쓰는 기술 따라잡기 바쁨
5. JAVA 조차 익숙하지 않던 시절에 너무 어려웠음

입사 시험으로 단골인걸 알면서도 애써 외면하고 있던 죄책감이 스멀스멀 쌓여서 다시 의지를 갖고 책을 폈다.
블로그도 시작해보려 야심차게 velog를 쓰고 있으니, 끝까지 해봐야지.

문제ID : FESTIVAL

정답은 모르겠고, 내마음대로 뚝딱거리면서 풀어봄.

Buffered...머시기 있었는데 하면서 기본적인 IO 방법부터 찾아가며 엄청 뚝딱거리며 풀어보았다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class p6 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int C = Integer.parseInt(br.readLine());

        for (int i = 0; i < C; i++) {
            String line = br.readLine();

            int N = Integer.parseInt(line.split(" ")[0]);
            int L = Integer.parseInt(line.split(" ")[1]);

            String costStr = br.readLine();
            String[] costStrArr = costStr.split(" ");

            int[] costs = new int[N];
            int[] costSums = new int[N];

            for (int j = 0; j < N; j++) {
                costs[j] = Integer.parseInt(costStrArr[j]);
                costSums[j] = j > 0 ? costSums[j - 1] + costs[j] : costs[j];
            }

            double minAvg = Float.MAX_VALUE;
            for (int days = L; days <= N; days++) {
                int sumCases = N - days + 1;
                int[] sumArr = new int[sumCases];

                for (int start = 0; start < sumCases; start++) {
                    sumArr[start] = costSums[start + days - 1] - (start > 0 ? costSums[start - 1] : 0);
                }

                minAvg = Math.min(minAvg, (double) Arrays.stream(sumArr).min().getAsInt() / days);
            }

            sb.append(String.format("%.8f", minAvg)).append("\n");
        }

        System.out.println(sb);
    }
}

해결 포인트

제일 처음에는 일단 모르겠고, 알고리즘 잘 기억안나니까 냅다 풀어보자 하면서 2중, 3중 for 문을 사용했다.

지금도 사실 정답(또는 괜찮은 답안)인지는 모르겠다. Algospot 사용법이 아직 익숙치 않아서 그런지 다른 분들이 제출한 답안들을 보고싶은데 볼 수 없는건지, 내가 찾지 못한건지 모르겠다.

나중에 알고보니 문제는 minAvg 변수의 float 자료형의 소수점 오차 때문이었는데, 허무하게도 double 로 변경하니 바로 해결되었다. 자료형에 대한 이해도 부족이라는 초보적인 실수..

처음 시도했던 무식한 방법인 2중, 3중 for문으로도 해결되었으려나 싶지만, 굳이 다시 시도해보진 않겠다.

input에서 새로운 배열을 생성해서 배열의 각 값까지의 총합을 costSums 배열에 저장하는 방식으로 문제를 해결했다.
평균을 계산해야 할 최소 일자는 L로 정해져있고, L 부터 N 까지의 일자 중 최소 평균 값을 계산하면 되기 때문에, 반복문을 사용해서 최소 일자부터 최대 일자까지 costs 배열의 start번째부터 days간의 총합을 구하면 days가 같은 총합으로 이루어진 sumArr배열이 완성되므로, 해당 배열에서 최소값만 찾으면 된다는 결론.

costSums 를 계산할때는 어차피 0번째 인덱스부터 현재까지의 총합을 구하는 것이기 때문에 이전 인덱스의 costSum + 현재값 을 계산하여 단일 반복문으로 간단하게 해결했고, days 반복문 안에서는 start 일자부터의 총합을 구했다.

나름 또 JAVA가 익숙해졌다고 stream을 이용한 최솟값도 찾고 그랬다만, 영 개운하지는 않다.
(IDE가 'OptionalInt.getAsInt()' without 'isPresent()' check warning을 계속해서 주고 있지만 애서 무시해본다...)

시도해본 것들

2
6 3
789 191 841 920 852 110
6 2
435 999 239 129 949 190

위 입력값을 입력했을 때, float 자료형을 활용했을 경우 첫번째 테스트 케이스에서 값이 582.8로 나와야 함에도 불구하고 계속해서 582.79998779로 나왔다.

1. 이중 배열을 이용하여 start부터 end까지의 총합을 input 입력시 계산해보려 했다. 예를들어 costSums[start][end] 값은 costs[start] ~ cost[end] 까지의 총합.
   - 결국 input 을 모두 저장한 뒤에 2중 반복문을 이용해야 했기 때문에 기존 방법과 다를게 없다고 판단하여 탈락.

2. JAVA 자료형과 관련하여 소수점 오차를 해결하는 방법을 검색해보았다. BigDecimal이라는 객체를 활용하는 방법이 나와 냅다 시도해보았다.
   - 결과는 동일한 오차 발생

이번에는 중간에 그만두지 않고 끝까지 공부해봐야지. 블로그도 열심히 써보고.