백준 1744번 - 수 묶기

문제

백준 1744번 - 수 묶기

아이디어

• 숫자를 양수와 0을 포함한 음수로 각각 저장한다.
• 양수는 최대한 큰 수끼리 묶어야 하고, 음수는 최대한 작은 수끼리 묶어야 한다.
• 양수를 묶을 때 주의해야 할 것은 1이다. 어떤 수에 1을 곱한 값보다 1을 더한 값이 더 크다.
• 음수를 묶을 때 특별히 주의해야 할 것은 없다. 음수끼리의 곱은 양수가 되고, 0을 곱해도 음수보다는 크기 때문이다.

예상 시간 복잡도

• 예상 시간 복잡도 : O(N)

코드 구현

package Baekjoon.greedy;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

public class BJ_1744 {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        ArrayList<Integer> positive = new ArrayList<>(); //양수
        ArrayList<Integer> negative = new ArrayList<>(); //음수

        for (int i = 0; i < n; i++) {
            int num = Integer.parseInt(br.readLine());

            if (num > 0) {
                positive.add(num);
            } else {
                negative.add(num);
            }
        }

        positive.sort(Collections.reverseOrder()); //양수 내림차순 정렬
        negative.sort(null);                    //음수 오름차순 정렬

        int sum = 0;

        for (int i = 0; i < positive.size(); i++) {
            if (i + 1 < positive.size() && positive.get(i) != 1 && positive.get(i + 1) != 1) {
                sum += positive.get(i++) * positive.get(i);
            } else {
                sum += positive.get(i);
            }
        }

        for (int i = 0; i < negative.size(); i++) {
            if (i + 1 < negative.size()) {
                sum += negative.get(i++) * negative.get(i);
            } else {
                sum += negative.get(i);
            }
        }

        System.out.println(sum);
    }
}