https://algospot.com/judge/problem/read/STRJOIN
algospot.com :: STRJOIN
문자열 합치기 문제 정보 문제 프로그래밍 언어 C 의 큰 문제점 중 하나는 언어 차원에서 문자열 변수형을 지원하지 않는다는 것입니다. C 에서는 문자 배열로 문자열을 표현하되 \0 (NULL) 로 문자
algospot.com
코드설명
그리디(탐욕법, 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;
}
}