[Do It! 코딩테스트 자바편(김종관)] 문제 034(백준: 1744번)

난이도

문제를 이해하고 구현하는 것은 어렵지 않다.

하지만 쉽다고 무작정 구현하면 수 많은 반례가 발생해서 포기하는 경우가 발생하고, 나 또한 그랬다.

문제

수를 묶어서 최댓값 만들기(백준: 1744번)

교재 풀이(맞는 풀이)

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

public class test {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt(); // 카드 묶음의 수 저장
    // 양수는 내림차순 정렬
    PriorityQueue<Integer> plusPq = new PriorityQueue<>(Collections.reverseOrder());
    PriorityQueue<Integer> minusPq = new PriorityQueue<>();
    int one = 0;
    int zero = 0;
    for (int i = 0; i < N; i++) { // 4개의 그룹으로 분리하여 저장
      int data = sc.nextInt();
      if (data > 1) {
        plusPq.add(data);
      } else if (data == 1) {
        one++;
      } else if (data == 0) {
        zero++;
      } else {
        minusPq.add(data);
      }
    }
    int sum = 0;
    // 양수처리
    while (plusPq.size() > 1) {
      int first = plusPq.remove();
      int second = plusPq.remove();
      sum = sum + first * second;
    }
    if (!plusPq.isEmpty()) {
      sum = sum + plusPq.remove();
    }
    // 음수처리
    while (minusPq.size() > 1) {
      int first = minusPq.remove();
      int second = minusPq.remove();
      sum = sum + first * second;
    }
    if (!minusPq.isEmpty()) {
      if (zero == 0) {
        sum = sum + minusPq.remove();
      }
    }
    // 1처리
    sum = sum + one;
    System.out.println(sum);
  }
}

내 풀이(틀린 풀이)

• 무작정 배열에 수열을 저장하고(어떻게 입력값을 저장하는게 더 다루기 쉬울 지 깊게 생각하지 않고) 이것저것 조건을 달면서 풀려고 했더니 런타임 에러(ArrayIndexOutOfBounds)나 그냥 틀린 경우가 생겼다.
• 반례를 찾아보고 그에 맞게 코드를 수정하면 또 다른 부분에서 반례가 끊임없이 생겨서 이 풀이를 그만두고 교재 풀이를 보게 되었다.

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int a[] = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }

        int sum = 0;
        if (a.length > 1) {
            Arrays.sort(a);
            // 양수 다 더함
            for (int i = n - 1; i >= 0; i -= 2) {
                if (a[i] > 0) {
                    int j = i - 1;
                    if (j < 0) {
                        sum += a[i];
                    } else {
                        if (a[j] > 0) {
                            if (a[i] == 1 || a[j] == 1) {
                                sum += a[i] + a[j];
                            } else {
                                sum += a[i] * a[j];
                            }
                        } else {
                            sum += a[i];
                            break;
                        }
                    }

                } else {
                    break;
                }
            }

            for (int i = 0; i < n; i += 2) {
                if (a[i] < 0) {
                    int j = i + 1;
                    if (j >= n) {
                        sum += a[i];
                    } else {
                        if (a[j] < 0) {
                            sum += a[i] * a[j];
                            break;
                        } else if (a[j] == 0) {
                            sum += a[i] * 0;
                            break;
                        } else {
                            sum += a[i];
                            break;
                        }
                    }
                } else {
                    break;
                }
            }
        } else {
            sum += a[0];
        }

        System.out.println(sum);

    }
}