[백준 - 1744] 수 묶기 .java

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

예제 
9
-1
-8
2
1
3
6
-5
0
1
출력
62

 

문제 분석

n의 최대 범위가 10,000이므로 시간 복잡도 관련 제약은 적다

-> 가능한 큰 수 끼리 곱하여 더한다

-> 음수끼리의 곱은 양수이며 음수 곱하기 0은 0임을 이용한다

1. 1보다 큰 양수, 1의 개수, 0의 개수, 음수의 4가지 유형으로 나눈다
2. 1보다 큰 양수: 최댓값부터 차례대로 곱하고 더한다 -> 홀수개이면 남은 한개는 더한다
3. 1의 개수: 개수만큼 더한다
4. 음수: 더 작은수를 곱해야 곱했을 때 큰 양수가 된다 -> 최솟값부터 곱하여 더한다.
5. 0의 개수: 음수가 홀수개이고 0의 개수가 1이상이면 남은 음수값을 더하지 않는다.(0과 곱했다고 생각하기)

즉, 1보다 큰 양수를 다루는 plusq는 내림차순, 음수를 다루는 minusq는 오름차순 정렬을 유지해야한다

-> 우선 순위 큐를 사용한다

 

• 각 큐 남은 1개의 처리 방법

-> while 조건을 size()>1로 설정하여 1개가 남으면 빠져나온다(짝수개이면 빈큐이기때문에 빠져나온다)

-> 비어있지 않으면 hap에 더한다

-> 음수의 경우 비어있지 않고 0이 없다면 결과에 더한다

 

 

 

import java.util.*;

public class Main {
    public static void main(String[] args)  {
        Scanner sc = new Scanner(System.in);
        // 입력 받아 저장
        int n = sc.nextInt();

        //우선순위 큐 - 양수의 내림차순
        PriorityQueue<Integer> plusq = new PriorityQueue<>(Collections.reverseOrder());
        //우선순위 큐 - 음수의 오름차순
        PriorityQueue<Integer> minusq = new PriorityQueue<>();
        //1의 개수
        int one = 0;
        //0의 개수
        int zero = 0;

        //입력받은거 나눠서 저장하기
        for(int i = 0; i < n; i++){
            int v = sc.nextInt();
            if(v > 1) plusq.add(v);
            else if(v == 1) one++;
            else if(v == 0) zero++;
            else minusq.add(v);
        }
        int hap = 0;
        //1처리
        hap += one;

        //양수 처리 - 큐에 하나만 남을 때까지
        while(plusq.size()> 1){
            int su1 = plusq.poll();
            int su2 = plusq.poll();
            hap += su1 * su2;
        }
        //하나의 값이 남았으면 더하기 처리
        if(!plusq.isEmpty()){
            hap += plusq.poll();
        }

        //음수 처리 - 큐에 하나만 남을 때까지
        while(minusq.size()>1){
            int su1 = minusq.poll();
            int su2 = minusq.poll();
            hap += su1 * su2;
        }
        //하나 값이 남았을 때 0이 있다면 더하지 않고 없으면 더하기
        if(!minusq.isEmpty()){
            if(zero == 0){
                hap += minusq.poll();
            }
        }
        System.out.println(hap);

    }

}