[자바/자료구조] 코드트리 IM : 최솟값 3개

https://www.codetree.ai/missions/8/problems/top-3-smallest-number?utm_source=clipboard&utm_medium=text 

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

 

알고리즘

간단하게 생각해서 최솟값 3개를 입력 받을때마다 빼고, 이를 곱한걸 출력하는 것이니, 입력 받을때마다 어떻게 최솟값을 뽑아낼지만 고민하면 된다. 중복되는 값이 존재할 수 있는 경우에서 최솟값을 매번 찾는 연산을 수행하려면 O(logN)으로 수행 가능한 우선순위 큐를 사용하면 좋다.

 

V1 : 틀림

처음엔 이게 왜 틀렸는지 알 수 없었다... 결론은 오버플로우 때문이다. int 타입끼리 3개만 곱하더라도 n의 최대가 100,000이므로 10^15제곱을 표현할 수 없는 int는 오버플로우가 발생할 수 밖에 없다. 이처럼 출력해야 하는 값이 매우 커지는 경우에는 그 피산 타입을 연산 전에 long으로 형변환해주는 작업이 필요하다. 앞으로는 절대 까먹지 말고 주의하자.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        Queue<Integer> queue = new PriorityQueue<>();
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            queue.add(Integer.parseInt(st.nextToken()));
            if (queue.size() < 3) {
                System.out.println(-1);
            } else {
                int p1 = queue.poll();
                int p2 = queue.poll();
                int p3 = queue.poll();
                System.out.println(p1 * p2 * p3);
                queue.add(p1);
                queue.add(p2);
                queue.add(p3);
            }
        }
    }
}

V2 : 정답

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        Queue<Integer> queue = new PriorityQueue<>();
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            queue.add(Integer.parseInt(st.nextToken()));
            if (queue.size() < 3) {
                System.out.println(-1);
            } else {
                long p1 = queue.poll();
                long p2 = queue.poll();
                long p3 = queue.poll();
                System.out.println(p1 * p2 * p3);
                queue.add((int)p1);
                queue.add((int)p2);
                queue.add((int)p3);
            }
        }
    }
}