[java]백준 1744번: 수 묶기, 그리디 알고리즘

https://www.acmicpc.net/problem/1744

1744번: 수 묶기

 

코드

 

package javaCodingTest;

import java.util.*;

public class j1744 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		//양수 우선순위큐 -> 내림차순으로 정렬, 내림차순 이유: 큰 값부터 우선으로 곱해주기 위해서
		PriorityQueue<Integer> p_pq = new PriorityQueue<>(Collections.reverseOrder());
		// 0,과 음수 우선순위큐-> 오름차순, 오름차순 이유: 곱해줬을 때 더 커지니까
		PriorityQueue<Integer> m_pq = new PriorityQueue<>();

		for (int i = 0; i < N; i++) {
			int data = sc.nextInt();
			if (data > 0) {
				p_pq.add(data);
			} else {
				m_pq.add(data);
			}

		}

		int data1 = 0;
		int data2 = 0;
		int sum = 0;
		while (p_pq.size() > 1) {
			//양수 우선순위큐가 2개 이상일 때 꺼내서 둘이 곱해줘서 더해준. ** 꺼낸 데이터가 1일 때는 곱해주지 않고 더해준다.

			data1 = p_pq.poll();
			data2 = p_pq.poll();
			if (data1 == 1 || data2 == 1) {
				sum += data1 + data2;
			} else {
				sum += data1 * data2;
			}

		}
		//남은 양수 우선순위 큐 하나는 더해준다.
		if (p_pq.size() == 1) {

			sum += p_pq.poll();
		}

		// 0과 음수 우선순위큐에서 2개 이상이면 서로 곱해줘서 더해준다.
		
		while (m_pq.size() > 1) {

			sum += m_pq.poll() * m_pq.poll();
		}
		// 남은 하나 더해준다.
		if (m_pq.size() == 1) {

			sum += m_pq.poll();
		}

		System.out.println(sum);

	}
}

 

풀이

 

그리디greedy 알고리즘:

현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘

 

 

그리디 알고리즘의 핵심 이론

① 해 선택: 현재 상태에서 가장 최선이라고 생각되는 해를 선택

 

② 적절성 검사: 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사

 

③ 해 검사: 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사. 전체 문제를 해결하지 못한다면 ①로 돌아가 같은 과정 반복

---

 

① 수의 집합을 양수 p_pq, (0,음수) m_pq 이렇게 2가지 유형으로 나눠 저장한다.

-> p_pq는 내림차순 우선순위큐로, m_pq는 오름차순 우선순위큐로 정렬

 

 

②-1  p_pq는 큰 값부터 차례대로 곱한 후 더한다. (내림차순 정렬)

->  p_pq에서 뽑은 수가 1일때는 곱하지 않고 그냥 더해준다.(1은 곱하는 것보다 더하는게 더 값이 커지니까)

-> p_pq의 크기가 1일때는 하나 남았으므로 더해준다.

 

②-2 m_pq는 작은 값부터 차례대로 곱한 후 더한다. (오름차순)

-> 음수는 작은 값을 서로 곱해줘야 값이 더 커지므로

-> m_pq의 크기가 1일때는 하나 남았으므로 더해준다.