[백준/JAVA] 1744번: 수 묶기

🔺 문제

1744번: 수 묶기

 

🔺 코드

- 틀림

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

        for(int i = 0 ; i < N ; i++) {
            int num = Integer.parseInt(br.readLine());
            pq.add(num);
        }

        int data1 = 0;
        int data2 = 0;
        int sum = 0;

        while(pq.size() != 1) {
            data1 = pq.poll();
            data2 = pq.poll();

            if(data1 > 0) {
                if(data2 <= 0)      sum = sum + (data1 + data2); 
                else if(data2 > 0)  sum += data1 * data2;
            } else if(data1 < 0) {
                if(data2 >= 0)      sum = sum + (data1 + data2);
                else if(data2 < 0)  sum += data1 * data2;
            } else if(data1 == 0) {
                if(data2 < 0) {
                    sum += data1 * data2;
                } else if(data2 > 0) {
                    sum = sum + (data1 + data2);
                }
            }
        }
        System.out.println(sum);
    }
}

죄다 조건 걸어서 풀어볼까 하고 시도했었다.. 

 

 

- 정답

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        PriorityQueue<Integer> plusQ = new PriorityQueue<>(Collections.reverseOrder());
        PriorityQueue<Integer> minusQ = new PriorityQueue<>();

        int one = 0;
        int zero = 0;

        for(int i = 0 ; i < N ; i++) {
            int num = Integer.parseInt(br.readLine());

            if(num == 0)        zero++;
            else if(num == 1)   one++;
            else if(num > 1)    plusQ.add(num);
            else if(num < 0)    minusQ.add(num);
        }

        int data1 = 0;
        int data2 = 0;
        int sum = 0;

        // 양수 우선순위 큐 크기가 2보다 작을 때까지
        while(plusQ.size() >= 2) {
            data1 = plusQ.remove();
            data2 = plusQ.remove();

            sum += data1 * data2;
        }

        // 큐에 데이터가 남아있으면
        if(!plusQ.isEmpty()) {
            sum += plusQ.remove();
        }

        // 음수 처리
        while(minusQ.size() >= 2) {
            data1 = minusQ.remove();
            data2 = minusQ.remove();

            sum += data1 * data2;
        }

        if(!minusQ.isEmpty() && zero == 0) {
            sum += minusQ.remove();
        }


        // 처리하기
        sum += one;	// 숫자 1 개수, 결과값에 저장
        System.out.println(sum);
    }
}

✅ 해결 아이디어
✔ 우선순위 큐 사용
- 가능한 큰 수끼리 묶기
- 수의 집합을 4분할 (1보다 큰 수 / 1 / 0 / 음수)

 

---

🔺 다른 풀이들

[백준 Gold 4] 1744 수 묶기 -Java

 

---

💬 느낀 점

어떤 조건식을 만들지..를 잘 생각해야 하는 것 같다.

 

 

1회독	2회독	3회독	4회독	5회독
V