[백준] 1744번. 수 묶기(JAVA)

문제

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

---

풀이(15분)

import java.io.*;
import java.util.*;

public class Main {

    // 양수의 경우 내림차순으로 해서 곱해서 더하자
    // 음수의 경우 오름차순으로 해서 곱해서 더하자
    // 0은 버리자

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int answer = 0;
        boolean isZero = false;
        
        PriorityQueue<Integer> positiveNums = new PriorityQueue<>((o1, o2) -> {
            if(o1 == o2){
                return o1 - o2;
            }
            return o2 - o1;
        }); // 양수는 내림차순

        PriorityQueue<Integer> negativeNums = new PriorityQueue<>(); // 음수는 오름차순

        for(int i = 0; i < n; i++){
            int input = Integer.parseInt(br.readLine());
            if(input == 0){ // 0의 경우 존재 자체가 중요함
                isZero = true;
                continue;
            }
            
            if(input < 0){ // 음수인 경우 무조건 음수 우선순위큐에
                negativeNums.add(input);
                continue;
            }
            
            if(input == 1){ // 1을 곱하는 것보다 더하는 것이 이득이므로
                answer += 1; // 바로 정답에 더함
                continue;
            }
            
            if(input > 0){ // 1을 제외한 양수 우선순위큐에 넣기
                positiveNums.add(input);
            }
        }

        int positiveNumsSize = positiveNums.size();
        int negativeNumsSize = negativeNums.size();

        for(int i = 0; i < positiveNumsSize / 2; i++){ // 짝수개씩 묶어서 더함
            int first = positiveNums.poll();
            int second = positiveNums.poll();
            answer += first * second;
        }
        if(!positiveNums.isEmpty()){ // 양수가 1개 남았다면
            answer += positiveNums.poll(); // 더해주기
        }

        for(int i = 0; i < negativeNumsSize / 2; i++){ // 짝수개씩 묶어서 더함
            int first = negativeNums.poll();
            int second = negativeNums.poll();
            answer += first * second;
        }
        if(!negativeNums.isEmpty()){ // 음수가 1개 남았다면
            if(isZero){ // 만약 0이 존재한다면
                System.out.println(answer); // 음수를 0과 곱해 무시할 것이기 때문에 그냥 출력
                return;
            }
            answer += negativeNums.poll(); // 음수 1개를 무시할 수 없으므로 더해주기
        }

        System.out.println(answer);

    }


}

---

문제 풀이 전략

 

사실 문제 자체는 매우 단순하다.

다만, 정확한 예제가 없었다면? 실수하기 너무나도 쉬운 문제이다. 꼭 꼼꼼하게 고민하고 풀이하자.

 

1. 양수는 내림차순으로 정렬한다.

2. 음수는 오름차순으로 정렬한다.

3. 이 두 개를 별도로 계산한다.

 

하지만 여기서 중요한 포인트가 몇 개 있다.

- 1과 2 모두 짝수의 개수만큼은 두 수를 곱해서 더한다. -> 그것이 최대가 될 수 있다.

- 0의 경우 제외한다.

- 1의 경우 곱해서 더하는 것보다 그냥 더하는 것이 이득이다.

 

즉 여기서 입력을 잘 파악해야한다.

0의 경우 단순하게 제외만 하면 끝일까? 

-> 아니다. 음수가 1개 남는 경우 이를 0을 곱해 같이 묶어서 없애버리자!!

-> 즉, 0은 몇 개가 나오는지는 중요하지 않지만 존재의 유무는 중요하다.

-> boolean 타입으로 처리하자.

 

1의 경우 곱해서 더하는 것보다 그냥 더하는 것이 이득이다.

-> 1의 경우 양수 우선순위 큐에 넣는 것이 아니라 바로 정답에 더해버리자!