Computer/알고리즘

[알고스팟] 문자열 합치기

alias 2016. 10. 3. 14:18
반응형

문제: 문자열합치기


이 문제는 

1) 현재 문자열중 가장 작은 길이 문자열 두개를 뽑아서 합친다.

2) 모든 문자열을 합칠 때까지 1)을 반복한다.


로 풀면 된다. 자바의 경우 PriorityQueue를 이용하면 쉽게 풀린다.



import java.util.PriorityQueue;
import java.util.Scanner;
public class Main {
private int mNumStr;
private PriorityQueue mPQ;
public Main(int numStr){
mNumStr=numStr;
mPQ=new PriorityQueue();
}
public void addNum(int num){
mPQ.add(num);
}
public void calculate(){
if(mPQ.size()==1) {
System.out.println(mPQ.remove());
return;
}
int costSum=0;
int before=(int)mPQ.remove();
for(int i=1;i<mNumStr;i++){
before=before+(int)mPQ.remove();
costSum=costSum+before;
mPQ.add((before));
before=(int)mPQ.remove();
}
System.out.println(costSum);
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc=new Scanner(System.in);
int caseCnt=sc.nextInt();
for(int caseIdx=0;caseIdx<caseCnt;caseIdx++){
int numStr=sc.nextInt();
Main solution=new Main(numStr);
for(int i=0;i<numStr;i++){
solution.addNum(sc.nextInt());
}
solution.calculate();
}
}
}
view raw STRJOIN.java hosted with ❤ by GitHub


반응형