[자바/자료구조] 코드트리 IM : 앞에서부터 삭제하기 2

https://www.codetree.ai/missions/8/problems/delete-it-from-the-beginning-2?utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

알고리즘

N이 최대 100,000이므로 2중 루프는 사용할 수 없으니, 경우의 수를 냅다 다 훑을 수 없으므로 완전탐색은 아니다. 

 

매번 k개의 숫자를 제거하는 연산은 불필요하며, 결국 모든 경우를 돌았을 때의 결론을 얻어내기 위해서는 주어진 숫자를 역순으로 입력받을 수 있으면 되니까 배열을 이용하여 인덱스를 거꾸로 순환하게끔 하면 된다.

 

평균을 구한 값은 중복 여부를 판단해야 하는 것이 아니며, 중복 여부에 관계없이 평균의 최대값만 구하면 되니까 우선순위 큐나 TreeSet 중에 아무거나 사용하면 될텐데, TreeSet이 더 간편하므로 이를 택했다. 최소값은 중복값이 있을 수 있으므로 우선순위 큐를 이용해서 선택해 주었다.

 

V1 : 시간초과

시간복잡도를 고려할 때, treeset이나 priority queue를 사용하면 그 자료구조와 관련된 연산까지는 O(logN)이기에 O(N*logN)으로 끝날 거라 생각했는데, 아무래도 stream을 이용하여 평균을 계산하는 것이 O(N)정도가 걸리는 것으로 보인다. 따라서 평균을 구하는 연산 과정을 좀 더 최적화해야 한다.

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

public class Main {
    private static int n;
    public static void main(String[] args) throws IOException {
        /*
        1번의 루프로,

        주어진 n개의 정수를 우선 배열로 받은 뒤, 역순으로 우선순위 큐와 리스트에 넣고,
        우선순위 큐의 poll() 내용을 리스트에서 제거하고
        list의 평균값을 계속 Double TreeSet에 넣어서 last() 출력
        **/
        Queue<Integer> queue = new PriorityQueue<>();
        TreeSet<Double> set = new TreeSet<>();
        List<Integer> li = new ArrayList<>();


        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[n];
        for (int i = n - 1; i >= 0; i--) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        for (int i = 0; i < n; i++) {
            int num = arr[i];
            li.add(num);
            queue.add(num);
            if (i < 2) {
                continue;
            }
            Integer poll = queue.poll();
            li.remove(poll);
            queue.add(poll);
            double avg = li.stream().mapToInt(e -> e).average().orElse(0);
            set.add(avg);
        }
        System.out.printf("%.2f", set.last());
    }
}

 

V2 : 통과

여기서도 컴퓨터의 연산 방식을 고려하지 않아서 한 차례 헤맸다.  우리가 얻어야 하는 것은 double 타입의 실수 값인데, 정수 나누기 정수를 수행하면 정수 값을 반환하며, 이를 연산이 끝난 후에 double로 형변환을 하면 그저 .00을 추가해줄 뿐이다. 하지만 문제에서는 더욱 정확한 평균값을 원하므로 나눗셈 연산을 하기 전에 각 분모와 분자를 double 타입으로 형변환 한 뒤에 연산값을 얻어내면 정확한 평균값을 얻어낼 수 있다.

package 코드트리.자료구조_중급.priorityQueue;

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

public class 앞에서부터_삭제하기 {
    private static int n;
    public static void main(String[] args) throws IOException {
        /*
        1번의 루프로,

        주어진 n개의 정수를 우선 배열로 받은 뒤, 역순으로 우선순위 큐와 리스트에 넣고,
        우선순위 큐의 poll() 내용을 리스트에서 제거하고
        list의 평균값을 계속 Double TreeSet에 넣어서 last() 출력
        **/
        Queue<Integer> queue = new PriorityQueue<>();
        TreeSet<Double> set = new TreeSet<>();

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[n];
        for (int i = n - 1; i >= 0; i--) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        int sum = 0;
        double avg = 0;
        for (int i = 0; i < n-1; i++) {
            int num = arr[i];
            sum += num;
            queue.add(num);
            if (i < 1) {
                continue;
            }
            Integer poll = queue.poll();
            avg = (double) (sum - poll) / (double) (queue.size()); // 헤맨 부분
            set.add(avg);
            queue.add(poll);
        }
        System.out.printf("%.2f", set.last());
    }
}