[java] 구름톤 6일차. 문자열 나누기

문제

길이가 N인 문자열 S가 주어진다. 플레이어는 문자열 S를 서로 겹치지 않는 3개의 부분 문자열로 나누려고 한다. 부분문자열은 모두 길이가 1 이상이어야 하며, 원래 문자열에서 연속해야 한다. 문자열을 나누는 방법에 따라 플레이어는 점수를 얻을 수 있다. 점수는 다음 과정에 따라 계산된다.
- 문자열 S를 위 조건에 따라 나눴을 때, 등장하는 모든 부분문자열을 중복 제거하고 사전순으로 정렬한 결과를 P라고 한다.
- 나누어진 3개의 문자열이 각각 P에서 i,j,k번째로 등장하는 문자열이라면, 얻을 수 있는 점수는 i+j+k이다.
예를 들어, abcd 라는 문자열을 3개의 부분 문자열로 나누는 방법은 {a,b,cd}, {a,bc,d}, {ab,c,d}의 세 가지가 있다. 여기서 부분 문자열을 중복 제거하고 사전 순서로 정렬한 결과 P는 a,ab,b,bc,c,cd,d 이다. 이때 {ab,c,d}로 문자열을 나눈 경우 얻을 수 있는 점수는 2+5+7 = 14점이고, 얻을 수 있는 최대 점수이다.

문자열 S를 3개의 부분 문자열로 나눴을 때 얻을 수 있는 점수 중 최대 점수를 출력하시오.

 

입력

첫째 줄에 문자열의 길이 정수 N이 주어진다.
둘째 줄에 문자열 S가 주어진다.
- 3 <= N <= 100
- S는 알파벳 소문자로만 구성되어 있다.

 

출력

문자열을 나눠서 얻을 수 있는 최대 점수를 출력한다.

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine()); // 문자열 길이 입력
        String input = br.readLine(); // 문자열 입력

        int maxScore = 0;
        String bestCombination = "";

        for (int i = N - 3; i >= 1; i--) {
            for (int j = N - 2; j >= i + 1; j--) {
                String third = input.substring(N - 1); // 세 번째 부분 문자열
                String second = input.substring(j, N - 1); // 두 번째 부분 문자열
                String first = input.substring(0, j); // 첫 번째 부분 문자열

                int score = calculateScore(first) + calculateScore(second) + calculateScore(third);
                if (score > maxScore) {
                    maxScore = score;
                    bestCombination = first + " " + second + " " + third;
                }
            }
        }

        System.out.println("최대 점수: " + maxScore);
        System.out.println("최대 점수를 얻는 문자열 조합: " + bestCombination);
    }

    public static int calculateScore(String s) {
        int score = 0;

        for (int i = 0; i < s.length(); i++) {
            score += s.charAt(i) - 'a' + 1; // 각 알파벳의 인덱스 값을 더함
        }

        return score;
    }
}

처음에 dfs를 생각 못하고 마구잡이로 풀었다가

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String word = br.readLine();

        List<List<String>> wsetList = new ArrayList<>();
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n - 1; j++) {
                List<String> wset = new ArrayList<>();
                int index = 0;
                for (int k : new int[]{i, j, n - 1}) {
                    wset.add(word.substring(index, k + 1));
                    index = k + 1;
                }
                wsetList.add(wset);
            }
        }

        Set<String> wlist = new HashSet<>();
        for (List<String> wset : wsetList) {
            wlist.addAll(wset);
        }
        List<String> sortedWlist = new ArrayList<>(wlist);
        Collections.sort(sortedWlist);

        int answer = 0;
        for (List<String> wset : wsetList) {
            int temp = 0;
            for (String w : wset) {
                temp += sortedWlist.indexOf(w) + 1;
            }
            answer = Math.max(answer, temp);
        }

        System.out.println(answer);
    }
}

로 해결

 

사실 dfs 알고리즘부터 건들지 못해서 진짜 나는 오래걸렸다.. 알고리즘 화이팅!