알고리즘 챌린지 6일차

문제

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

코드

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

public class Day21_34 {
    public static void main(String[] args){
        Scanner scan =new Scanner(System.in);
        int N=scan.nextInt();   //카드 묶음의 수 저장하기
        int one=0,zero=0;
        //양수는 내림차순으로 정렬하기
        PriorityQueue<Integer> positive=new PriorityQueue<>(Collections.reverseOrder());
        PriorityQueue<Integer> negative=new PriorityQueue<>();

        for(int i=0;i<N;i++){       //4개의 그룹으로 분리해 저장하기
            int data=scan.nextInt();
            if(data>1){
                positive.add(data);
            }else if(data==1){
                one++;
            }else if(data==0){
                zero++;
            }else{
                negative.add(data);
            }
        }

        int sum=0;
        //양수 처리하기
        while (positive.size()>1){
            int data1=positive.remove();
            int data2=positive.remove();
            sum=sum+data1*data2;
        }
        if(!positive.isEmpty()){
            sum=sum+ positive.remove();
        }
        //음수 처리하기
        while (negative.size()>1){
            int data1=negative.remove();
            int data2=negative.remove();
            sum=sum+data1*data2;
        }
        if(!negative.isEmpty()&&zero==0){
            sum=sum+ negative.remove();
        }
        //1 처리하기
        sum=sum+one;
		System.out.print(sum);
    }
}

풀이

N의 최대 범위가 10,000이므로 시간 복잡도와 관련된 제약이 적은 문제다.
가능한 큰 수들끼리 묶어야 결과값이 커진다. 음수끼리 곱하면 양수가 되는 것도 생각하면서 풀어야한다.
먼저 4가지 유형으로 나누어 생각해야한다.1보다 큰 수, 1, 0, 음수로 나누어 저장한다.

• 1보다 큰 수의 집합을 정렬해 최댓값부터 차례대로 곱한 후 더해준다. 홀수일 때 마지막 남은 수는 그냥 더해준다.
• 음수의 집합을 정렬해 최소값부터 차례대로 곱한 후 더해준다. 홀수일 때 0이 있다면 마지막 남은 수를 0과 곱해서 0을 만들고, 0이 없다면 마지막 남은 수를 그냥 더해준다.
• 위의 두 결과를 더한값에 1의 갯수를 더해준다.

후기

처음에는 우선순위 큐를 한개만 이용하려고 해서 계속 막혔었다. 2개(음수, 1보다 큰 양수) 유형의 큐를 생성해주는 것이 이 문제의 포인트였다. 1보다 큰 양수는 Collections.reverseOrder()를 이용해 내림차순으로 정렬해주는 것이 디테일인 것 같다.