[종만북][알고스팟] 문자열 합치기 (STRJOIN) - 그리디(탐욕법, Greedy) JAVA

https://algospot.com/judge/problem/read/STRJOIN

algospot.com :: STRJOIN

코드설명

그리디(탐욕법, Greedy) 을 활용합니다. 

 

가장 짧은 두 개의 문자열을 가장 빨리 더해가면서 진행해야 합니다.

계속해서 이 문자열들이 더해지면서 문자열들의 길이가 계속 누적되기에 최대한 앞부분에서는 짧게 더해줌으로써 누적합을 작게해주어야합니다.

코드

package Main;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class Main {
	private static int N, K, M;
    private static int answer = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int C = Integer.parseInt(st.nextToken());
        while(C-- > 0) {
        	st = new StringTokenizer(br.readLine());
        	N = Integer.parseInt(st.nextToken());
        	
        	st = new StringTokenizer(br.readLine());
        	PriorityQueue<Integer> pq = new PriorityQueue<>();
        	for(int i=0; i<N; i++) {
        		pq.offer(Integer.parseInt(st.nextToken()));
        	}
        	System.out.println(concat(pq));
        }
    }
    
    private static int concat(PriorityQueue<Integer> pq) {
    	int ret = 0;
    	//원소가 하나 이상 남은 동안 반복한다.
    	while(pq.size() > 1) {
    		//가장 짧은 문자열 두 개를 합치고 큐에 넣는다.
    		int min1 = pq.poll();
    		int min2 = pq.poll();
    		int sum = min1 + min2;
    		pq.offer(sum);
    		ret += sum;
    	}
    	return ret;
    }
    
}