[구름톤 챌린지] Day 6 문자열 나누기

문제

---

길이가 N인 문자열 S가 주어진다. 플레이어는 문자열 S를 서로 겹치지 않는 3개의 부분문자열로 나누려고 한다. 부분문자열은 모두 길이가1이상이어야 하며, 원래 문자열에서 연속해야 한다.

문자열을 나누는 방법에 따라 플레이어는 점수를 얻을 수 있다. 점수는 다음 과정에 따라 계산된다.

• 문자열 를 위 조건에 따라 나눴을 때, 등장하는 모든 부분문자열을 중복 제거하고 사전순으로 정렬한 결과를 라고 한다.
• 나누어진 개의 문자열이 각각 에서 번째로 등장하는 문자열이라면, 얻을 수 있는 점수는 이다.

예를 들어, abcd 라는 문자열을 3 개의 부분문자열로 나누는 방법은 {a, b, cd}, {a, bc, d}, {ab, c, d} 의 세 가지가 있다. 여기서 부분문자열을 중복 제거하고 사전 순서로 정렬한 결과 P는 a, ab, b, bc, c, cd, d 이다. 이때 {ab, c, d} 로 문자열을 나눈 경우 얻을 수 있는 점수는

점이고, 얻을 수 있는 최대 점수이다.

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

 

입력

---

첫째 줄에 문자열의 길이 정수 N이 주어진다.둘째 줄에 문자열 S가 주어진다.

• 는 알파벳 소문자로만 구성되어 있다.

 

출력

---

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

 

예시

입력

4
abcd

출력

14

 

접근 방법 및 풀이

---

완전 탐색 문제이다. 자를 수 있는 문자열을 보두 잘라서 중복을 제거하고, 정렬해서 P를 만들면 된다.

 

풀이 방법

1. 문자열을 3개로 나눠 set에 넣는다. (중복이 없어야하기 때문에)
2. 리스트 P에 set을 담은 후 정렬을 해준다.
3. map에 인덱스와 단어를 담는다.
4. 최댓값을 찾는다.

 

코드

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;


public class Main {

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

        List<String[]> wordList = new ArrayList<>();
        Set<String> set = new HashSet<>();

        for (int i = 1; i < N; i++) {
            for(int j = i + 1; j < N; j++) {
                String first = str.substring(0, i);
                String second = str.substring(i, j);
                String third = str.substring(j);
                wordList.add(new String[]{first, second, third});

                set.add(first);
                set.add(second);
                set.add(third);
            }
        }

        List<String> P = new ArrayList<>(set);
        Collections.sort(P);

        Map<String, Integer> map = new HashMap<>();
        int index = 1;
        for(String word : P) {
            map.put(word, index++);
        }

        int max = -1;
        for (String[] words : wordList) {
            int first = map.get(words[0]);
            int second = map.get(words[1]);
            int third = map.get(words[2]);

            max = Math.max(max, first + second + third);
        }
        System.out.println(max);
    }
}