[백준 1744번] 수 묶기 (Java 풀이)

백준알고리즘 1744번 : 수 묶기

 

문제에 대한 대략적인 설명

 

 

곱하거나 더함으로써 정수 집합의 최댓값을 만들어 내는 문제이다.

처음에는 집합을 하나의 배열로 만들어 정렬한다음에 양의 정수와 그렇지 않은 정수로 구분하여 계산해주려고 했다.

그러나 그렇게 되면 배열을 어디서부터 끊어야할지 계산하는 것이 너무 복잡하여(집합의 길이가 짝수냐, 양수의 갯수가 짝수냐 등등..)

고민끝에 ArrayList로 양의 정수와 0이하의 정수를 구분하여 받아 정렬해주었다.

이렇게 되면 편한점은, 각 ArrayList들끼리만 정렬을 한뒤에 최댓값을 셈해주고, 남은 것들을 계산해주면 된다.

음의 정수는 작은 숫자들끼리 곱할수록 더 큰 정수를 만들수 있고(-11)*(-10) > (-5)*(-4),

양의 정수는 말할것도 없기 때문이다.

변수는 1과 0인데, (곱셈이 덧셈보다 더 작은 case) 이를 차단해버리기 위해서 for문을 돌때마다 if문을 걸어 곱셈이 덧셈보다 클때는 곱셈 결과값을,

그렇지 않을 때는 덧셈 결과값을 더하도록 해주었다.

 

풀이 과정

---

1. ArrayList를 2개 정의하여, 하나는 양의 정수를, 하나는 0보다 작거나 같은 정수를 받는다.
2. ArrayList를 정렬한다.(양의 정수는 내림차순, 음의 정수는 오름차순)
3. 각 ArrayList의 값을 계산한뒤에, 잔여 정수가 있다면 따로 계산해준다.

 

 

 

소스 ▽

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

public class Main {// No1744 : 수 묶기

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int nums = Integer.parseInt(br.readLine());
        int[] arr = new int[nums];
        int ans = 0;

        ArrayList<Integer> arrPos = new ArrayList<>();
        ArrayList<Integer> arrNeg = new ArrayList<>();

        for (int i = 0; i < nums; i++) {
            int num = Integer.parseInt(br.readLine());
            if (num > 0) {
                arrPos.add(num);
            } else {
                arrNeg.add(num);
            }
        }

        Collections.sort(arrPos, Collections.reverseOrder());
        Collections.sort(arrNeg);

        for (int i = 0; i < arrPos.size() - arrPos.size() % 2; i += 2) {
            if (arrPos.get(i) * arrPos.get(i + 1) > arrPos.get(i) + arrPos.get(i + 1)) {
                ans += arrPos.get(i) * arrPos.get(i + 1);
            } else {
                ans += arrPos.get(i) + arrPos.get(i + 1);
            }
        }

        for (int i = 0; i < arrNeg.size() - arrNeg.size() % 2; i += 2) {
            if (arrNeg.get(i) * arrNeg.get(i + 1) > arrNeg.get(i) + arrNeg.get(i + 1)) {
                ans += arrNeg.get(i) * arrNeg.get(i + 1);
            } else {
                ans += arrNeg.get(i) + arrNeg.get(i + 1);
            }
        }

        boolean surplusPos = false;
        boolean surplusNeg = false;
        if (arrPos.size() % 2 != 0 && arrNeg.size() % 2 != 0) {
            if (arrPos.get(arrPos.size() - 1) * arrNeg.get(arrNeg.size() - 1) > arrPos.get(arrPos.size() - 1) + arrNeg.get(arrNeg.size() - 1)) {
                ans += arrPos.get(arrPos.size() - 1) * arrNeg.get(arrNeg.size() - 1);
            } else {
                ans += arrPos.get(arrPos.size() - 1) + arrNeg.get(arrNeg.size() - 1);
            }
        } else if (arrPos.size() % 2 != 0) {
            ans += arrPos.get(arrPos.size() - 1);
        } else if (arrNeg.size() % 2 != 0) {
            ans += arrNeg.get(arrNeg.size() - 1);
        }

        System.out.println(ans);
    }
}