JAVA 백준 1744 수 묶기 (정렬)

 

https://www.acmicpc.net/problem/1744

---

문제

1. 첫째 줄에 N ( 1 <= N <= 50 ) 입력.
2. 둘째 줄부터 N개의 줄에 수열의 수 주어짐 ( -1000 <= 수열의 수 <= 1000 ) 
3. 주어진 수 N개를 최대가 나오게 묶는다.
4. 괄호로 묶는 것은 두 개의 수를 위치에 상관 없이 최대가 되도록 골라 두 수를 곱한다.

---

 

 

 

초기 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        ArrayList<Integer> arr = new ArrayList<>();

        int result = 0;

        for (int i = 0; i < N; i++) {
            arr.add(Integer.parseInt(br.readLine()));
        }

        Collections.sort(arr);

        while (!arr.isEmpty()) {
            if (arr.size() == 1) {
                result += arr.get(0);
                arr.remove(0);
            } else {
                if (arr.get(0) < 0) {
                    if (arr.contains(0)) {
                        result += arr.get(0) * arr.get(arr.indexOf(0));
                        arr.remove(0);
                        arr.remove(arr.indexOf(0));
                    } else if (arr.get(1) < 0) {
                        result += arr.get(0) * arr.get(1);
                        arr.remove(0);
                        arr.remove(0);
                    }else{
                        result += arr.get(0);
                        arr.remove(0);
                    }
                } else if (arr.get(arr.size() - 1) * arr.get(arr.size() - 2) > arr.get(arr.size() - 1) + arr.get(arr.size() - 2)) {
                    result += arr.get(arr.size() - 1) * arr.get(arr.size() - 2);
                    arr.remove(arr.size() - 1);
                    arr.remove(arr.size() - 1);
                } else {
                    result += arr.get(arr.size() - 1) + arr.get(arr.size() - 2);
                    arr.remove(arr.size() - 1);
                    arr.remove(arr.size() - 1);
                }
            }
        }

        System.out.println(result);
    }
}

 40퍼센트 쯤에서 틀렸다.

예제는 다 맞았는데 반례를 찾아봐야 될 것 같다.

 

 

최종 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        ArrayList<Integer> arr = new ArrayList<>();

        long result = 0;

        for (int i = 0; i < N; i++) {
            arr.add(Integer.parseInt(br.readLine()));
        }

        Collections.sort(arr);

        while (!arr.isEmpty()) {
            if (arr.size() == 1) {
                result += arr.get(0);
                arr.remove(0);
            } else {
                if (arr.get(0) < 0) {
                    if (arr.get(1) < 0) {
                        result += arr.get(0) * arr.get(1);
                        arr.remove(0);
                        arr.remove(0);
                    } else if (arr.contains(0)) {
                        result += arr.get(0) * arr.get(arr.indexOf(0));
                        arr.remove(0);
                        arr.remove(arr.indexOf(0));
                    } else {
                        result += arr.get(0);
                        arr.remove(0);
                    }
                } else if (arr.get(arr.size() - 1) * arr.get(arr.size() - 2) > arr.get(arr.size() - 1) + arr.get(arr.size() - 2)) {
                    result += arr.get(arr.size() - 1) * arr.get(arr.size() - 2);
                    arr.remove(arr.size() - 1);
                    arr.remove(arr.size() - 1);
                } else {
                    result += arr.get(arr.size() - 1) + arr.get(arr.size() - 2);
                    arr.remove(arr.size() - 1);
                    arr.remove(arr.size() - 1);
                }
            }
        }

        System.out.println(result);
    }
}

 

3

0

-1

-8

이라는 반례를 찾아서 그거에 맞게 수정했다.

 

 

고친 부분은

if (arr.get(0) < 0) {
    if (arr.get(1) < 0) {
        result += arr.get(0) * arr.get(1);
        arr.remove(0);
        arr.remove(0);
    } else if (arr.contains(0)) {
        result += arr.get(0) * arr.get(arr.indexOf(0));
        arr.remove(0);
        arr.remove(arr.indexOf(0));
    } else {
        result += arr.get(0);
        arr.remove(0);
    }
}

 

이 if문에서 0이 들어있을 때 가장 작은 수를 곱하는 것이 먼저가 아니라

가장 작은 수가 음수이고 그 다음으로 작은 수가 음수일 때 그 둘을 곱해 큰 양수를 만드는 부분을 먼저 계산할 수 있도록 했다.