[종만북] STRJOIN - 문자열 합치기 (자바 java)

알고리즘 문제해결전략(종만북) 스터디 메인 페이지

목차

문제 : aoj-STRJOIN

 

 

풀이

  N개의 문자열이 주어질 때, 여기서 2개를 선택해 새로운 문자열을 만들고, 그 길이의 합이 비용이 된다. 이걸 하나의 문자열만 남을 때 까지 반복하는 문제이다.

 

  합치는 순서가 중요할텐데, 4개의 문자열이 있고 각 길이가 A, B, C, D라고 해보자. (A)와 (B)를 합치면 (A+B)의 문자열이 된다. 그럼 문자열은 현재 (A+B), (C), (D)가 있다. (A+B)와 (C)를 합치면 (A+B+C)가 된다. 그리고 다시 (D)와 합치면 (A+B+C+D)가 된다. 여기서 비용에 들어간 횟수를 살펴보면 'A'와 'B'는 비용에 총 3번, 'C'는 2번, 'D'는 1번 더해졌다. 따라서 직관적으로 여러번 합쳐질 녀석은 길이가 작은 것일수록 좋다는걸 알 수 있다.

 

  또 문자열을 합치는 횟수는 항상 N-1번이다. 횟수는 조정할 방법이 없다. 따라서 풀이는 그냥 매번 현재 문자열들 중 길이가 가장 작은 2개를 매번 더해서 새로운 문자를 만들어주면 된다.

 

  내 경우엔 우선순위큐를 사용해 구현했다. 처음 N개의 길이를 전부 큐에 넣고, 2개를 빼서 더한값을 다시 큐에 넣는 식으로 큐에 1개의 값만 남을 때 까지 계속한다(혹은 N-1번 수행하면 된다.). 

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws Exception {
        int c = Integer.parseInt(br.readLine().trim());
        while (c-->0) new Main().solution();
        System.out.print(sb);
    }

    private void solution() throws Exception {
        int n = Integer.parseInt(br.readLine());
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        StringTokenizer st = new StringTokenizer(br.readLine());
        while (n-->0) pq.add(Integer.parseInt(st.nextToken()));

        int sum = 0;
        while (pq.size() != 1) {
            int joinCost = pq.poll() + pq.poll();
            sum += joinCost;
            pq.add(joinCost);
        }

        sb.append(sum).append('\n');
    }
}

 

 

※ 종만북에 이미 풀이가 있는데 제 풀이를 올리는 이유는 제가 책의 풀이를 보지 않고 문제를 푼 후 제 풀이를 올리고 나서 책의 풀이를 보는 방식으로 풀어보고 싶기 때문입니다.