Computer/알고리즘
[알고스팟] 문자열 합치기
alias
2016. 10. 3. 14:18
반응형
문제: 문자열합치기
이 문제는
1) 현재 문자열중 가장 작은 길이 문자열 두개를 뽑아서 합친다.
2) 모든 문자열을 합칠 때까지 1)을 반복한다.
로 풀면 된다. 자바의 경우 PriorityQueue를 이용하면 쉽게 풀린다.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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(); | |
} | |
} | |
} |
반응형