[백준] 수 묶기(1744번)

문제 힌트

1. 자료구조

• 음수, 양수 리스트
  
  • 음수는 음수끼리 양수는 양수끼리 곱을 하여 관리하기 위해 자료구조 분리
  • 이유 : 음수의 갯수가 홀수 일 때 관리의 번거로움이 생김
• Collections.sort()
  • 리스트에 값을 전부 저장하고 정렬하기
  • 이유: 1 2 3 4 5가 주어졌을 때 가장 큰 수는 5*4 + 3*2 + 1이 가장 높은 수 이기 때문
• boolean zeroFlag
  • 0이 있는지 여부를 저장
  • 이유 : 0은 사용하지 않는 음수가 있을 때 곱을 하여 해당 음수를 0으로 만들어 가장 큰 수로 만들 수 있음
  • 0이 2개 이상일 경우 몇 개가 있어도 의미가 없는 숫자이기 때문에 boolean으로 관리

 

2. 핵심 아이디어

• 리스트를 사용한 정렬 및 분류
  음수와 양수를 분리하여 정렬하고 각각 계산하므로, 구조가 간단하면서도 효율적입니다.
• 짝수 처리
  두 개씩 묶어 최대값을 계산하는 방식은 곱셈과 덧셈을 비교하여 최적화된 값을 보장합니다.
• 홀수 처리와 0의 역할
  0이 있는 경우, 음수 리스트의 마지막 숫자를 곱함으로써 음수의 영향을 제거합니다.

 

3. 로직

• 입력 분류 및 초기화
  • 입력받은 숫자를 음수, 양수로 나누어 저장하고, 0이 포함되어 있는지 확인합니다.
• 리스트 정렬
  • 음수 리스트는 오름차순 정렬(작은 값부터 큰 값으로).
  • 양수 리스트는 내림차순 정렬(큰 값부터 작은 값으로).
• 짝수 개의 숫자 묶기
  • 음수와 양수를 각각 인접한 두 숫자로 묶어 최대값(덧셈 vs 곱셈)을 계산합니다.
• 남는 숫자 처리
  • 음수 리스트에 남는 숫자가 홀수 개일 경우, 0이 없으면 그대로 결과에 더합니다.
  • 양수 리스트에 남는 숫자가 홀수 개일 경우, 그대로 결과에 더합니다.
• 최종 출력
  • 결과값을 출력합니다.

정답은 더보기 클릭

---

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 입력을 빠르게 처리하기 위한 BufferedReader
    
    public static void main(String[] args) throws IOException {
        int N = Integer.parseInt(br.readLine()); // 입력받는 정수의 개수

        // 음수와 양수를 나누어 저장할 리스트 및 0 여부를 체크하는 플래그
        List<Integer> negativeNumberList = new ArrayList<>();
        List<Integer> positiveNumberList = new ArrayList<>();
        boolean zeroFlag = false; // 0이 입력되었는지 확인하는 플래그

        // 입력받은 숫자들을 분류
        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(br.readLine());

            if (num < 0) {
                negativeNumberList.add(num); // 음수는 음수 리스트에 추가
            } else if (num > 0) {
                positiveNumberList.add(num); // 양수는 양수 리스트에 추가
            } else {
                zeroFlag = true; // 0이 있음을 체크
            }
        }

        // 음수 리스트는 오름차순 정렬
        Collections.sort(negativeNumberList);
        // 양수 리스트는 내림차순 정렬
        Collections.sort(positiveNumberList, Collections.reverseOrder());

        long result = 0; // 최종 결과값을 저장할 변수

        // 음수 리스트에서 인접한 두 숫자를 묶어 계산
        for (int i = 0; i < negativeNumberList.size() - 1; i += 2) {
            result += Math.max(negativeNumberList.get(i) + negativeNumberList.get(i + 1),
                    negativeNumberList.get(i) * negativeNumberList.get(i + 1));
        }

        // 양수 리스트에서 인접한 두 숫자를 묶어 계산
        for (int i = 0; i < positiveNumberList.size() - 1; i += 2) {
            result += Math.max(positiveNumberList.get(i) + positiveNumberList.get(i + 1),
                    positiveNumberList.get(i) * positiveNumberList.get(i + 1));
        }

        // 음수 또는 양수 리스트 중 하나가 비어있을 경우 처리
        if (negativeNumberList.isEmpty() || positiveNumberList.isEmpty()) {
            // 음수 리스트의 남은 숫자가 홀수 개일 경우
            if (negativeNumberList.size() % 2 == 1 && !zeroFlag) {
                result += negativeNumberList.get(negativeNumberList.size() - 1);
            } 
            // 양수 리스트의 남은 숫자가 홀수 개일 경우
            else if (positiveNumberList.size() % 2 == 1) {
                result += positiveNumberList.get(positiveNumberList.size() - 1);
            }

            System.out.println(result); // 결과 출력 후 종료
            return;
        }

        // 양수와 음수 리스트가 모두 비어있지 않은 경우
        int posLastNum = positiveNumberList.get(positiveNumberList.size() - 1); // 양수 리스트의 마지막 숫자
        int negLastNum = negativeNumberList.get(negativeNumberList.size() - 1); // 음수 리스트의 마지막 숫자

        // 음수 리스트의 남은 숫자가 홀수 개이고 0이 없을 경우 처리
        if (!zeroFlag && negativeNumberList.size() % 2 == 1) {
            result += negLastNum;
        }

        // 양수 리스트의 남은 숫자가 홀수 개일 경우 처리
        if (positiveNumberList.size() % 2 == 1) {
            result += posLastNum;
        }

        System.out.println(result); // 최종 결과 출력
    }
}