![[java] 백준 1744번 문제(수 묶기)](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2F49FC1%2FbtsNaEpa5bg%2Fucp1BQ7mtmaJ9S8VQYjsX1%2Fimg.png)
[java] 백준 1744번 문제(수 묶기)자료구조 & 알고리즘/BOJ2025. 4. 7. 11:41
Table of Contents
원본 링크 : 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은 음수가 홀수개 일 때, 음수를 합계에 더하는 것을 막는용으로 사용된다.
- 나머지 자세한 내용은 주석 참고
'자료구조 & 알고리즘 > BOJ' 카테고리의 다른 글
[java] 백준 1931번 문제(회의실 배정) (0) | 2025.04.08 |
---|---|
[java] 백준 1715번 문제(카드 정렬하기) (0) | 2025.04.07 |
[java] 백준 1300번 문제(K번째 수) (0) | 2025.04.03 |
[java] 백준 2343번 문제(기타 레슨) (0) | 2025.04.02 |
[java] 백준 1167번 문제(트리의 지름) (0) | 2025.03.31 |