자료구조 & 알고리즘/BOJ

[java] 백준 1744번 문제(수 묶기)

seungwook_TIL 2025. 4. 7. 11:41

원본 링크 : https://www.acmicpc.net/problem/1744


문제설명

 

 

소스코드

방법 1

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class Boj_1744
{
    public static void main(String[] args) throws IOException
    {
        List<Integer> positives = new ArrayList<>(); // 2 이상
        List<Integer> negatives = new ArrayList<>(); // 음수
        boolean existsZero = false; // 0의 존재 유무
        int sum = 0;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        for (int i = 0; i < n; ++i)
        {
            int number = Integer.parseInt(br.readLine());
            if(number > 1) positives.add(number);
            else if(number == 1) ++sum;
            else if(number == 0) existsZero = true;
            else negatives.add(number);
        }
        Collections.sort(positives, Comparator.reverseOrder()); // 내림차순
        Collections.sort(negatives); // 오름차순

        // 양수 처리
        for (int i = 0; i < positives.size() - 1; i += 2) sum += positives.get(i) * positives.get(i + 1);
        if (positives.size() % 2 == 1) // 양수의 개수가 홀수라면
        {
            sum += positives.get(positives.size() - 1); // 가장 작은 양수를 더함
        }

        // 음수 처리
        for (int i = 0; i < negatives.size() - 1; i += 2) sum += negatives.get(i) * negatives.get(i + 1);
        if (negatives.size() % 2 == 1) // 음수의 개수가 홀수라면
        {
            if (!existsZero) sum += negatives.get(negatives.size() - 1); // 0의 개수가 없을 때 합계에 음수를 더함
        }

        System.out.print(sum);
    }
}

 

방법 2

package Onlne_Judge.rank3_gold.rank4;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.Collections;

public class Boj_1744
{
    public static void main(String[] args) throws IOException
    {
        PriorityQueue<Integer> positives = new PriorityQueue<>(Collections.reverseOrder()); // 2 이상
        PriorityQueue<Integer> negatives = new PriorityQueue<>(); // 음수
        boolean existsZero = false; // 0의 존재 유무
        int sum = 0;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        for (int i = 0; i < n; ++i)
        {
            int number = Integer.parseInt(br.readLine());
            if(number > 1) positives.offer(number);
            else if(number == 1) ++sum;
            else if(number == 0) existsZero = true;
            else negatives.offer(number);
        }

        // 양수 처리
        while(positives.size() > 1)
        {
            int first = positives.poll();
            int second = positives.poll();
            sum += first * second;
        }
        if(!positives.isEmpty()) sum += positives.poll();

        // 음수 처리
        while(negatives.size() > 1)
        {
            int first = negatives.poll();
            int second = negatives.poll();
            sum += first * second;
        }
        if(negatives.size() == 1) // 음수의 개수가 홀수라면
        {
            if(!existsZero) sum += negatives.poll(); // 0이 없을 때만 음수를 더함
        }

        System.out.print(sum);
    }
}

 

설명

  • 2 이상의 양수, 1, 0, 음수 이렇게 4가지로 나눠서 생각해야한다.
  • 2 이상의 양수는 내림차순으로 정렬시킨다.
  • 음수는 오름차순으로 정렬시킨다.
  • 1은 무조건 단순히 더해야한다.
  • 0은 음수가 홀수개 일 때, 음수를 합계에 더하는 것을 막는용으로 사용된다.
  • 나머지 자세한 내용은 주석 참고