[코딩테스트] 백준 1744 자바

백준 1744

백준 1744 문제

해당 문제는 가능한 한 큰 수들끼리 묶어야 결괏값이 커진다는 것을 알 수 있다.

또한 음수끼리 곱하면 양수로 변하는 성질을 추가로 고려해 문제를 푸는 것이 좋다.

import java.util.*;

public class Boj1744 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 수의 개수

        PriorityQueue<Integer> plusQueue = new PriorityQueue<>(Collections.reverseOrder()); // 양수 우선순위 큐(내림차순 정렬)
        PriorityQueue<Integer> minusQueue = new PriorityQueue<>(); // 음수 우선순위 큐
        int one = 0; // 1의 개수 카운트
        int zero = 0; // 0의 개수 카운트

        for (int i = 0; i < n; i++) { // n만큼 반복
            int data = sc.nextInt();

            // 데이터를 4개의 그룹에 분리 저장
            if (data > 1) {
                plusQueue.offer(data);
            } else if (data == 1) {
                one++;
            } else if (data == 0) {
                zero++;
            } else {
                minusQueue.offer(data);
            }
        }

        int sum = 0; // 결괏값

        while (plusQueue.size() > 1) { // 양수 우선순위 큐 크기가 2보다 작을 때까지 반복
            // 수 2개를 큐에서 뽑음
            int first = plusQueue.poll();
            int second = plusQueue.poll();

            sum += first * second; // 2개의 수를 곱한 값을 결괏값에 더함
        }

        if (!plusQueue.isEmpty()) { // 양수 우선순위 큐에 데이터가 남이있으면
            sum += plusQueue.poll(); // 이 데이터를 결괏값에 더함
        }

        while (minusQueue.size() > 1) { // 음수 우선순위 큐 크기가 2보다 작을 때까지 반복
            // 수 2개를 큐에서 뽑음
            int first = minusQueue.poll();
            int second = minusQueue.poll();

            sum += first * second; // 2개의 수를 곱한 값을 결괏값에 더함
        }

        if (!minusQueue.isEmpty()) { // 음수 우선순위 큐에 데이터가 남이있고
            if (zero == 0) { // 데이터 0이 1개도 없으면
                sum += minusQueue.poll(); // 이 데이터를 결괏값에 더함
            }
        }

        sum += one; // 숫자 1의 개수를 결괏값에 더함
        System.out.println(sum); // 결괏값 출력
    }
}

문제풀이

1. 수의 개수를 n으로 입력 받아 저장한다.
2. 양수를 저장할 그룹을 plusQueue 우선순위 큐로 선언한다.(큰 수부터 나올 수 있도록 내림차순 정렬을 해준다.)
3. 음수를 저장할 그룹을 minusQueue 우선순위 큐로 선언한다.
4. 1의 개수를 카운트할 one을 0으로 초기화한다.
5. 0의 개수를 카운트할 zero를 0으로 초기화한다.
6. n만큼 반복하며 입력된 데이터를 data에 저장한다.
7. data를 4개의 그룹에 분리 저장한다.
   1. data가 1보다 크면 plusQueue에 저장한다.
   2. data가 1이면 one 수를 증가시킨다.
   3. data가 0이면 zero 수를 증가시킨다.
   4. data가 그 외이면(1보다 작으면) minusQueue에 저장한다.
8. 결괏값 sum을 0으로 초기화한다.
9. 먼저 양수 그룹 plusQueue의 크기가 2보다 작을 때까지 아래 과정 반복한다.
   1. 수 두 개를 꺼내서 각각 first와 second에 저장한다.
   2. sum에 first와 second의 곱을 더한다.
10. plusQueue에 데이터가 남아있으면 sum에 남은 데이터를 더한다.
11. 음수 그룹 minusQueue의 크기가 2보다 작을 때까지 아래 과정 반복한다.
    1. 수 두 개를 꺼내서 각각 first와 second에 저장한다.
    2. sum에 first와 second의 곱을 더한다.
12. minusQueue에 데이터가 남아있고 0의 개수 zero가 0이면 남은 데이터를 더한다.
13. 1의 개수 one을 sum에 더한다.
14. sum을 출력한다.