문제사항

골드 4단계 문제였다.

묶는 수는 두 개의 수를 곱한 값이기 때문에 양수와 음수로 구분지어야 한다.

• 양수일 때
  • 큰 값 * 큰 값
  • 하지만 값이 1이라면 더한다 (1은 연속으로 나올 수 있음 주의)
  • 마지막 값이 하나라면 더해야한다.
• 음수일 때
  • 작은 값 * 작은값
  • 하지만 값이 0이라면 queue에서 꺼내기만 한다. (어차피 0이기 때문에 더해도 무용지물. 묶는 수로는 작용하면 곱할 시에 값을 0으로 만들기 때문에 사용하면 안됨)
  • 마지막 값이 하나라면 더해야한다.

알고리즘 분류

1. 그리디 알고리즘

2. 정렬

코드

import java.io.*;
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());
        PriorityQueue<Integer> positive = new PriorityQueue<>(Collections.reverseOrder());
        PriorityQueue<Integer> negative = new PriorityQueue<>();
        int answer = 0;

        for (int i = 0; i < n; i++) {
            int num = Integer.parseInt(br.readLine());
            if(num <= 0) {
                negative.add(num); //0을 포함한 음수
            }
            else {
                positive.add(num); //0보다 큰 양수
            }
        }

        while (!negative.isEmpty()) {
            int num = negative.poll();
            if (negative.isEmpty()) { //꺼낸 값 num이 마지막 값이면 더한 후 빠져나온다.
                answer += num;
                break;
            }
            if (negative.peek() == 0) { //이후에 꺼낸 값이 0일 때 꺼내버린다.
                negative.poll();
            } else { //0이 아니면 num과 곱한다.
                answer += num * negative.poll();
            }
        }

        while (!positive.isEmpty()) {
            int num = positive.poll();
            if (positive.isEmpty()) { //꺼낸 값 num이 마지막 값이면 더한 후 빠져나온다.
                answer += num;
                break;
            }
            if (num == 1) { //꺼낸 값 num이 1이면 answer에 더하기
                answer += 1;
            } else if (positive.peek() == 1) { //num이 1이 아니되, 이후에 꺼낸 값이 1이면 num과 더한다.
                answer += num + positive.poll();
            } else {
                answer += num * positive.poll(); //num이 1이 아니고, 이후에 꺼낸 값도 1이 아니면 num과 이후에 꺼낸 값을 곱한다.
            }
        }

        System.out.println(answer);
    }
}