정렬_1744_수 묶기

지난 시간과 마찬가지로 오늘도 정렬과 그리디 알고리즘을 사용하여 풀 수 있는 문제를 풀어보자. 
지난번보다는 난이도를 조금 올려서 이번엔 골드 4로 책정된 문제이다. 조금 까다로워 보이긴 하지만 문제의 조건을 세밀하게 따져가면서 풀어보자. 

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

1744번: 수 묶기

 

1. 문제 분석 

• 수열의 원소의 최대합을 구한다. 
• 원소는 두 개만 한쌍으로 묶을 수 있고, 각 원소는 1번 이하로만 묶일 수 있다.  (0 or 1)
• 묶인 두 수는 곱하여 합을 구해야 한다. 
• 수열의 최대 크기는 50, 각 원소의 크기는 -1000~1000이며, 정답으로 나올 수 있는 값의 최대 값은 2^31이다. 즉 최댓값을 담을 변수는 int자료형을 초과하기 때문에 long형을 사용해야 한다. 

 

2. 문제 접근 

• 곱의 합의 최대를 구하기 위해선 음수는 음수끼리 곱하고, 양수는 양수끼리 곱해서 절댓값의 곱의 합이 최대가 되어야 한다. 
• 이때 각 케이스 별로 따져야 하는 부분이 있는데 음수는 0, 양수는 1이다. 
• 먼저, 음수의 개수가 짝수개라면 모든 음수를 한 번씩 묶어서 합을 양수로 만들 수 있지만, 음수의 개수가 홀수 개라면 남은 하나의 음수를 그대로 더할지 0과 묶어서 소거할지를 처리해야 한다. 
• 다음으로, 양수의 개수는 단순히 양의 정수가 아니라 1보다 큰 양의 정수를 구해야 한다. 
  • 대부분이 음수와 양수를 나누고 0까지는 생각했겠지만 1을 놓쳐서 문제를 풀지 못했을 것이다.  
  • 그냥 양수끼리 곱하게 되었을 때, 1의 존재는 자기 자신의 역할을 하지 못한다. 
  • 예를 들어 양수의 리스트가 {1,2,3,4}라고 했을 때, 1*2 + 3*4 = 14가 최대 일 것 같지만, 1+2+3*4=15가 더 크다. 
  • 1과 2를 곱해서 2를 만들면서 1이 덧셈을 했을 때 할 수 있는 자신의 역할을 포기하면서 더 작아진 셈이다. 
• 마지막으로, 위에서 제외한 0과 1을 모두 더해주면 된다.

 

3. 코드 구현

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.stream.Collectors;

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

        Long answer = 0L;
        boolean isZero = false;                 //0이 있다면 true

        int N = Integer.parseInt(br.readLine());
        ArrayList<Integer> nums = new ArrayList<>();
        
        //수열 초기화
        for(int i=0; i<N; i++){
            nums.add(Integer.parseInt(br.readLine()));
            if(nums.get(i) == 0) isZero = true;
        }

        //음수 리스트 (0보다 작은 값들만 추출, 내림차순 정렬(=절댓값 기준 오름차순) -> ex){-1, -2, -3, -4})
        List<Integer> negativeList = nums.stream().filter(val -> val < 0).sorted(Comparator.reverseOrder()).collect(Collectors.toList());

        //특이값 리스트 (0과 1만 추출 ; 리스트로 뽑는 이유는 수열의 원소가 중복이지 않다는 조건이 없기 때문이다. )
        List<Integer> specialList = nums.stream().filter(val -> val == 0 || val == 1).collect(Collectors.toList());

        //양수 리스트 (1보다 큰 양의 정수 추출, 오름차순 정렬 -> ex) {1,2,3,4})
        List<Integer> positiveList = nums.stream().filter(val -> val > 1).sorted().collect(Collectors.toList());

        if(positiveList.size() > 0){
            if (positiveList.size() % 2 == 0){ //짝수
                for(int i= positiveList.size()/2; i>0; i--){
                    answer += positiveList.get(2*i-1)*positiveList.get(2*(i-1));
                }
            }else { //홀수인 경우 첫 번째 값(제일 작은 것)은 그냥 더하고 나머지는 곱의합을 더한다. 
                answer += positiveList.get(0);
                for(int i= positiveList.size()/2; i>0; i--){
                    answer += positiveList.get(2*i)*positiveList.get(2*i-1);
                }
            }
        }

        if(negativeList.size() > 0){
            if (negativeList.size() % 2 == 0){ //짝수
                for(int i= negativeList.size()/2; i>0; i--){
                    answer += negativeList.get(2*i-1)*negativeList.get(2*(i-1));
                }
            }else { //홀수인 경우에는 0이 있는 경우에는 어차피 곱이 0이기 때문에 무시. 없는 경우만을 생각해서 그대로 더해주기
                if(!isZero) answer += negativeList.get(0); 
                for(int i= negativeList.size()/2; i>0; i--){
                    answer += negativeList.get(2*i)*negativeList.get(2*i-1);
                }
            }
        }

        //제외 시켰던 특이케이스 모두 더하기(0은 더해도 뭐 상관없잖아?)
        answer += specialList.stream().mapToInt(val -> val).sum();
        System.out.println(answer);
    }
}