[java] 문제 034 (백준 1744)

문제

수 묶어서 최댓값 만들기

 

교재 풀이

import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Scanner;
public class P1744_수묶기 {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt(); // 카드 묶음의 수 저장
    // 양수는 내림차순 정렬
    PriorityQueue<Integer> plusPq = new PriorityQueue<>(Collections.reverseOrder());
    PriorityQueue<Integer> minusPq = new PriorityQueue<>();
    int one = 0;
    int zero = 0;
    for (int i = 0; i < N; i++) { // 4개의 그룹으로 분리하여 저장
      int data = sc.nextInt();
      if (data > 1) {
        plusPq.add(data);
      } else if (data == 1) {
        one++;
      } else if (data == 0) {
        zero++;
      } else {
        minusPq.add(data);
      }
    }
    int sum = 0;
    // 양수처리
    while (plusPq.size() > 1) {
      int first = plusPq.remove();
      int second = plusPq.remove();
      sum = sum + first * second;
    }
    if (!plusPq.isEmpty()) {
      sum = sum + plusPq.remove();
    }
    // 음수처리
    while (minusPq.size() > 1) {
      int first = minusPq.remove();
      int second = minusPq.remove();
      sum = sum + first * second;
    }
    if (!minusPq.isEmpty()) {
      if (zero == 0) {
        sum = sum + minusPq.remove();
      }
    }
    // 1처리
    sum = sum + one;
    System.out.println(sum);
  }
}

 

내 풀이) 24.6.18에 풀었지만, 예제 케이스 이상하게 출력된 틀린 코드

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

public class Main
{
	public static void main(String[] args) throws IOException{
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        PriorityQueue<Integer> plusPq=new PriorityQueue<>(Collections.reverseOrder());
        PriorityQueue<Integer> minusPq=new PriorityQueue<>();
        boolean isZero =false;
        Queue<Integer> ans=new LinkedList<>();
            
        for(int i=0;i<n;i++){
            int now=sc.nextInt();
            if(now>0) {
                plusPq.add(now);
            }else if(now==0){
                isZero=true;
            }else{
                minusPq.add(now);
            }
        }
        
        while(plusPq.size()>0&&minusPq.size()>0&&isZero==true){
            while(plusPq.size()>1){
                int e1=plusPq.remove();
                int e2=plusPq.remove();
                ans.add(e1*e2);
            }
            if(plusPq.size()==1){
                ans.add(plusPq.remove());
            }
            
            while(minusPq.size()>1){
                int e1=plusPq.remove();
                int e2=plusPq.remove();
                ans.add(e1*e2);
            }
            if(plusPq.size()==1 && isZero){
                ans.add(minusPq.remove()*0);
                isZero=false;
            }
        }
        
        int maxSum=0;
        for(int i:ans){
            maxSum+=i;
        }
        System.out.println(maxSum);
	}       
}

//길이가 N인 수열 -> 수열의 합
//    어떤 수를 묶으려고 할 때, 위치에 상관없이 묶을 수 있다. 
//    묶게 되면, 수열의 합을 구할 때 묶은 수는 서로 곱한 후에 더한다.
//    수열의 각 수를 적절히 묶었을 때, 그 합이 최대가 되게 하는 프로그램
//
//첫째 줄에 수열의 크기 N : 50보다 작은 자연수
//둘째 줄부터 N개의 줄에 수열의 각 수
//    수열의 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수
//수를 합이 최대가 나오게 묶었을 때 합을 출력한다. 정답은 항상 231보다 작다.
//    즉 int가 4바이트, 32비트, int로 충분하네 
//
//입력
//4
//-1
//2
//1
//3
//    n이 4이고 
//출력
//6    
//
//
//접근법
//    그리디임은 알고 있음, 우선순위 큐도 알고 있음
//    그러니까 두 수를 묶을 때 규칙은
//        최대한 큰 두 수끼리 묶는 거임
//    또 예외 처리로
//        음수의 경운, 음수끼리 그리고 절댓값 큰 것끼리 묶고 
//        음수가 있으면, 우선적으론 0이 있는지 보고 있으면 곱해줘서 없애야 함
//        그리고 0이 없고 음수가 남으면 그냥 냅둬야 함. 
//    또 우선순위 큐를 여러 종류로 만들어야 함.
//        양수만 담은 큐 
//        음수만 담은 큐 
//        0도 처리할 큐  
//        결과 배열 ans 
//    그럼 어떻게 묶지? 
//        양수의 경운 내림차순으로 정렬 후 
//        큰 거 두 개끼리 묶으면, 즉 곱한 값을 결과 배열에 담을까? 
//        
//슈도코드
//    n을 입력받음 
//    plusPq: collections.reverseOrder()를 넣어서 내림차순으로 
//    minusPq
//    zeroQ
//    ans
//    
//    for n번 반복해서 
//        수열을 받는데 
//        if 양수면 
//            양수 큐에 add 
//        if 0이면 
//            zeroQ에 add
//        else 
//            minusPq에 add 
//    
//    while plusPq, minusPq, zeroQ에 사이즈가 전부 0일 때 까지 반복
//        while 양수 큐 사이즈 > 1일 때까지
//            두 개 꺼내고 곱해서 
//            ans에 넣기
//        if(양수 큐 사이즈==1)
//            그거 그대로 ans에 넣기 
//        
//        while 음수 큐 사이즈 > 1일 때까지 
//            두 개 꺼내고 곱해서 
//            ans에 넣기 
//        if(음수 큐 사이즈 ==1){
//            if 0이 있다면
//                ans에 0을 넣기 
//        }

 

설명

24.6.18) 내 코드는 논리상 1을 다루는 부분이 없네. 또 음수 하나 남을 때 0을 처리하는 부분도 이상하고