수 묶기(백준 1744번)

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

1744번: 수 묶기

 

문제 설명

-1 -8 2 1 3 6 -5 0 1 이 주었다고 가정하자. 

(-8 * -5) + (-1 * 0) + 1 + 1 + 2 + (3 * 6)  = 62 이다.

 

문제에 대한 아이디어

이 문제는 그리디 알고리즘으로 풀어야 하는 이유가 매 순간 제일 최대의 값을 구해야 하기 때문이다. 

 

실패한 아이디어

제일 처음 문제를 풀 때는 엄청 간단하게 생각했다.

오름차순으로 배열을 정렬 시킨 뒤 맨 뒤에서 부터 2개씩 묶어서 더하도록 만들었다. (선택 절차)

 

문제점

• 양수와 음수를 곱하게 된다.
• 수열에 0이 존재하면 0과 양수를 곱하게 된다.
• 수열에 1이 존재한다면 1은 그냥 더하는 것이 곱하는 것보다 값을 더 크게 만든다.

 

성공한 아이디어

위에 문제점을 토대로 보완한 해결책이다.

• 우선순위 큐를 사용하여 양수와 음수를 따로 보관하자.
• 우선순위 큐의 양수 부분은 내림차순으로 설정, 우선순위 큐의 음수 부분은 오름차순으로 설정
• 0과 1도 따로 생각해자.
• 양수 부분은 우선순위 큐에서 2개를 빼 곱한뒤 결과값에 더하자.(반복)
• 만약 양수 부분에 수가 남았으면 결과값에 더한다.
• 음수 부분은 우선순위 큐에서 2개를 빼 곱한뒤 결과값에 더하자.(반복)
• 만약 음수 부분에 수가 남았고 0이 존재하면 그 수는 결과값에 더하지 않는다. 

 

구현

• 우선순위 큐 

PriorityQueue<Integer> plusPq = new PriorityQueue<>(Collections.reverseOrder());
PriorityQueue<Integer> minusPq = new PriorityQueue<>();
int one =0;
int zero =0;
for (int i = 0; i < n; i++) {
    int num = sc.nextInt();
    if(num > 1) plusPq.add(num);  //1을 제외한 양수 부분
    else if(num == 1) one++; // 1
    else if(num == 0) zero++; // 0
    else if(num < 0) minusPq.add(num); //음수 부분
}

• 양수 부분

//양수부분
while(plusPq.size()>1){
    int first = plusPq.poll();
    int second = plusPq.poll();
    result += first * second;
}
if(!plusPq.isEmpty()){
    result += plusPq.poll();
}

• 음수 부분

//음수부분
while(minusPq.size()>1){
    int first = minusPq.poll();
    int second = minusPq.poll();
    result += first * second;
}
if(!minusPq.isEmpty()){
    if(zero != 0){
        result += 0 * minusPq.poll();
        --zero;
    }
    else result += minusPq.poll();

 

전체 코드

import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n= sc.nextInt();
        PriorityQueue<Integer> plusPq = new PriorityQueue<>(Collections.reverseOrder());
        PriorityQueue<Integer> minusPq = new PriorityQueue<>();
        int one =0;
        int zero =0;
        for (int i = 0; i < n; i++) {
            int num = sc.nextInt();
            if(num > 1) plusPq.add(num);  //1을 제외한 양수 부분
            else if(num == 1) one++; // 1
            else if(num == 0) zero++; // 0
            else if(num < 0) minusPq.add(num); //음수 부분
        }
        int result =0;

        //양수부분
        while(plusPq.size()>1){
            int first = plusPq.poll();
            int second = plusPq.poll();
            result += first * second;
        }
        if(!plusPq.isEmpty()){
            result += plusPq.poll();
        }

        //음수부분
        while(minusPq.size()>1){
            int first = minusPq.poll();
            int second = minusPq.poll();
            result += first * second;
        }
        if(!minusPq.isEmpty()){
            if(zero != 0){
                result += 0 * minusPq.poll();
                --zero;
            }
            else result += minusPq.poll();
        }
        result += one;
        System.out.println(result);
    }
}