[코드트리 챌린지] 세 수의 최대 곱(S3)

Q. 세 수의 최대 곱

코드트리의 난이도와 백준의 난이도는 기준이 다르지만, 실버 3 난이도의 문제이다.

 

정수 n과 n개의 수가 주어졌을 때, 3개의 숫자를 적절하게 골라 나올 수 있는 곱 중 최대값을 구하는 프로그램을 작성하는 문제이고, n의 범위와 주어지는 수의 범위는 아래와 같다.

• 3 ≤ n ≤ 100,000
• -1,000 ≤ 주어지는 수 ≤ 1,000

첫 번째 줄에 3개의 숫자를 적절하게 골라 나올 수 있는 곱 중 최대값을 출력하면 된다.

 

풀이는 아래와 같다.

1. 음수와 양수를 다른 리스트에 저장한다.

2. 이 음수와 양수들을 각각 정렬한다 (이때 양수는 오름차순으로 정렬되므로 -를 붙이면 내림차순으로 정렬하는 효과가 있다)

3. 최대값이 나올 수 있는 각각의 케이스를 골라 계산한다

3 - 1. 문제를 풀다가 0을 무시했는데, 최대값이 음수인 경우 0이 들어왔다면 0이 최대값이 되므로 이 케이스를 고려해준다.

 

시간복잡도를 계산하면

1. 음수, 양수 정렬 - O(2 * n log n)이고

나머지는 상수 시간에 계산이 가능하다.

 

코드는 아래와 같다

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();

    static int n;

    static long res = Long.MIN_VALUE;

    static ArrayList<Integer> plusArr;
    static ArrayList<Integer> minusArr;

    static void input() throws IOException{

        n = Integer.parseInt(br.readLine());
        plusArr = new ArrayList<>();
        minusArr = new ArrayList<>();

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            int j = Integer.parseInt(st.nextToken());
            if (j == 0) {
                res = 0;
                continue;
            }
            if (j > 0) plusArr.add(-j);
            else minusArr.add(j);
        }
    }

    static void pro() {


        Collections.sort(plusArr);
        Collections.sort(minusArr);

        // 양수 * 양수 * 양수
        if (plusArr.size() >= 3) {
            res = (long)plusArr.get(0) * plusArr.get(1) * -plusArr.get(2);
        }
        // 양수 * 음수 * 음수 -> 정답이 양수인 경우
        if (minusArr.size() >= 2 && plusArr.size() > 0) {
            res = Math.max(res, (long)minusArr.get(0) * minusArr.get(1) * -plusArr.get(0));
        }
        // 음수 * 음수 * 음수
        if (plusArr.size() == 0) {
            res = Math.max(res, (long) minusArr.get(minusArr.size() - 1) * minusArr.get(minusArr.size() - 2) * minusArr.get(minusArr.size() - 3));
        }

        if (plusArr.size() > 1 && minusArr.size() > 0) {
            res = Math.max(res, (long)minusArr.get(minusArr.size() - 1) * plusArr.get(plusArr.size() - 1)* plusArr.get(plusArr.size() - 2));
        }

        System.out.println(res);


    }

    public static void main(String[] args) throws Exception{
        // 여기에 코드를 작성해주세요.
        input();
        pro();
    }
}