[Algorithm] 99클럽 코테 스터디 17일차 TIL BOJ 11399

문제

https://www.acmicpc.net/problem/11399

풀이

문제 분석

• 앞에서 소요되는 시간이 적을수록 대기시간 + 인출하는데 걸리는 시간이 짧기 때문에 사람이 돈을 뽑는데 걸리는 시간을 오름차순으로 정렬하여 답을 구할 수 있는 문제이다
• 부분합을 구하는 방식과 유사하다고 생각했다

코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int answer = 0;
        int N = Integer.parseInt(st.nextToken());
        int[] times = new int[N];
        int[] preSum = new int[N];
        st = new StringTokenizer(br.readLine());

        for (int i = 0; i < N; i++) {
            times[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(times);

        preSum[0] = times[0];
        for (int i = 1; i < N; i++) {
            preSum[i] = preSum[i-1] + times[i];
        }

        for(int sum : preSum) {
            answer += sum;
        }

        bw.write(String.valueOf(answer));
        bw.flush();
        bw.close();
    }
}

TIL

• 정답을 맞춘 후 코드를 더 간결하게 고치기 위해 부분합을 구하는 부분과 answer를 업데이트하는 for문을 하나로 묶어보았다
• 이 방식을 사용하면 preSum이라는 배열이 불필요해진다

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int answer = 0;
        int N = Integer.parseInt(st.nextToken());
        int[] times = new int[N];
        st = new StringTokenizer(br.readLine());

        for (int i = 0; i < N; i++) {
            times[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(times);

        int prev = 0;
        for (int i = 0; i < N; i++) {
            answer += prev + times[i];
            prev += times[i];
        }

        bw.write(String.valueOf(answer));
        bw.flush();
        bw.close();
    }
}

• 그러나 채점 결과를 비교해보면 두 코드의 소요시간은 동일하고 메모리에서만 차이를 보였다
  
• O(n)으로 동일해서 그런 것 같긴한데, input 데이터가 test 마다 달라져서인지는 2번째 케이스에 시간이 좀 더 걸린건가? 싶긴했다
• 결론적으로 확인할 수 있는 차이는 메모리였고, 이는 preSum 배열을 사용하지 않아서 나온 결과로 추측된다