[구름톤 챌린지, Java] 6일차, 문자열 나누기(완전 탐색)

문제 링크

구름LEVEL

---

접근 방법

이 문제에 핵심

1. 길이가 N인 문자열을 연속되게 3개의 부분 문자열로 나눌 수 있습니다.

2. 문자열을 나누었을 때 사전순으로 정렬한 결과를 P라고 합니다.

3. 나누어진 문자열 3개가 P에서 i, j, k값이 인덱스일 때 얻는 점수는 i + j + k입니다. 

4. 문자열이 얻을 수 있는 점수의 최대값을 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 나눌 수 있는 문자열을 모두 구해서 정렬한 뒤, 나뉘는 문자열의 최대 점수를 탐색합니다.

 

3. 최대 점수를 결과로 출력합니다.

 

 

구현

 

문자열을 3개로 나누는 모든 경우를 탐색합니다.

 

Ex. abc

 

[a, b, c]

 

정렬하면

 

a	b	c
1	2	3

 

3개 나올 수 있는 경우

 

{a, b, c}

 

a : 1

b : 2

c : 3

 

i  + j + k = 1 + 2 + 3 = 6

 

 

예제입력 1.

1. 입력된 정보를 저장합니다.

 

 

N : 4

 

S : abcd

 

 

2. 나눌 수 있는 문자열을 모두 구해서 정렬한 뒤, 나뉘는 문자열의 최대 점수를 탐색합니다.

 

나눌 수 있는 모든 문자열

 

{a, bc, d}

{a, b, cd}

{ab, c, d}

 

정렬 진행!

 

a	ab	b	bc	c	cd	d
1	2	3	4	5	6	7

 

3개 나올 수 있는 경우

 

{a, bc, d} : 1 + 4 + 7 = 12

 

{a, b, cd} : 1 + 3 + 6 = 10

 

{ab, c, d} : 2 + 5 + 7 = 14

 

3. 최대 점수를 결과로 출력합니다.

 

{ab, c, d} : 2 + 5 + 7 = 14

 

14을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 입력값들을 띄어쓰기 기준 나눕니다.
• search함수를 통해 문자열을 3개로 나눌 때 나오는 문자열을 모두 구합니다.
• TreeSet으로 오름차순 정렬된 문자열을 HashMap에 저장합니다.
• cal함수를 통해 문자열을 3개로 나눈 모든 경우에서 얻는 점수의 최대값을 구합니다.
• 구한 최대값을 결과로 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

• search함수는 재귀를 통해서 문자열을 3개로 나눌 때 생기는 모든 문자열을 구합니다.
• cal함수는 재귀를 통해서 모든 문자열의 경우에서 얻는 점수의 최대값을 구합니다.

 

결과코드

import java.util.*;
import java.io.*;
class Main {
    static int N;	//문자열 길이
    static String str;		//입력 받는 문자열
    static Set<String> set;		// 3개로 나눌 때 나올 수 있는 문자열 정보
    static String[] P = new String[3];	//현재 3개의 문자열을 나눈 정보
    static int result = -1;		// 최대값
    static Map<String, Integer> map;	//내림차순 정보 저장
    public static void main(String[] args) throws Exception {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        set = new TreeSet<>();	//TreeSet을 이용해 오름차순 정렬도 진행
        //입력값 저장
        N = Integer.parseInt(br.readLine());
        str = br.readLine();
        //나올 수 있는 모든 경우 탐색
        search(0, 2);
        //모든 경우 사전순 오름차순의 Index값을 HashMap<>에 저장
        map = new HashMap<>();
        int index = 1;
        for(String s : set){
            map.put(s, index++);
        }
        //모든 경우에서 최대값 탐색
        cal(0, 2);
        //최대값 BufferedWriter 저장
        bw.write(String.valueOf(result));
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //문자열 모든 경우 탐색하는 함수
    private static void search(int start, int cnt) {
        //3개로 나누어졌을 때
        if(cnt == 0){
            set.add(str.substring(start));
            return;
        }
        //문자열 나누는 과정
        for(int i=start+1;i<=N-cnt;i++){
            set.add(str.substring(start, i));
            search(i, cnt-1);
        }
    }
    //문자열 모든 경우에서 i + j + k을 통해 최대값 구하는 함수
    private static void cal(int start, int cnt) {
        //문자열 완성시
        if(cnt == 0){
            //최대값과 i + j + k 비교
            result = Math.max(result,map.get(str.substring(start)) + map.get(P[1]) + map.get(P[2]));
            return;
        }
        //문자열 나누는 과정
        for(int i=start+1;i<=N-cnt;i++){
            P[cnt] = str.substring(start, i);
            cal(i, cnt-1);
        }
    }
}

 

---

느낀 점

 

TreeSet을 이용해서 문제를 간단히 해결하려고 했지만, TreeSet에는 indexOf을 지원하지 않기 때문에 i + j + k의 연산을 진행할 때 for문을 돌리는 것이 비효율적이라고 생각하였습니다.

 

그래서, 다시 HashMap에 값을 저장한 뒤 O(1)으로 탐색할 수 있도록 하였습니다.

 

자료 구조에 대해서 다시 찾아보는 계기가 되었습니다.