[Java] 구름톤 챌린지 2주차 : 문자열 나누기

- 문제설명

 

- 해결과정

1. 문자열을 세 덩어리로 분리하고, 각 덩어리를 HashSet에 저장 (중복방지)
2. 세 덩어리를 하나의 결과로 본다. 해당 결과를 배열의 형태(String[])로 리스트에 저장한다.
3. 세 덩어리로 분리가능한 모든 경우를 순회해 1,2번 과정을 끝냈다면, 인덱스를 얻기위해 HashSet에 저장한 덩어리들을 리스트로 옮긴다. 이후 오름차순 정렬
4. 2번 과정을 통해 세 덩어리로 묶인 혹은 세 덩어리로 쪼개질 수 있는 모든 경우의 수를 알아냈다. 하나씩 꺼내면서 최댓값이 될 수 있는지 3번에서 얻은 리스트의 인덱스를 활용하여 판단해보면 된다.

 

주어진 문자열 S를 세 덩어리로 쪼개는 방식이 중요하다고 생각한다. 

1. 세 덩어리로 쪼개진 부분문자열은 모두 이어져야 한다.

2. 각 덩어리는 1개 이상의 문자를 포함해야한다.

위 두 가지 조건을 고려했을 때 최선의 선택은 substring을 사용하는 방식이었다.

최소 1개 이상의 문자를 포함하기위해서 변수들의 범위를 설정하고

 

String a = substring(0, i)

String b = substring(i, j)

String c = substring(j)

 

부분문자열을 위와 같이 세 개로 쪼개면 가장 효율적이라 판단했다.

추가로 이렇게 부분문자열을 쪼갰을 때 바로 new String[]{a, b, c}를 통해 해당 세트를 리스트에 보관해뒀기 때문에,

실제 세 덩어리의 부분문자열에 대해 인덱스 값을 계산해줄 때 추가적인 작업 필요없이 리스트에서 값을 꺼내와서 손쉽게 작업할 수 있었다.

 

- 솔루션

import java.io.*;
import java.util.*;
class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int N = Integer.parseInt(br.readLine());
		String S = br.readLine();
		List<String> list = new ArrayList<>();
		List<String[]> record = new ArrayList<>();
		Set<String> set = new HashSet<>();
        
        
		/*
			세 덩이로 분리되는 모든 부분문자열 찾기
			1. 중복을 제거하기 위해 각 부분문자열을 우선 해시셋에 저장
			2. 한번의 for문으로 나온 세 덩이의 부분문자열의 세트를 따로 배열의 형태로 record라는 이름의 리스트에 저장
				--> 여기에 저장된 세트를 꺼내서 maxIndex를 계산할 것임
		*/
		for(int i = 1; i <= N - 2; i++) {
			for(int j = i+1; j < N; j++) {
				set.add(S.substring(0, i));
				set.add(S.substring(i, j));
				set.add(S.substring(j));
				record.add(new String[]{S.substring(0, i), S.substring(i, j), S.substring(j)});
			}
		}
        
        
		/*
			해시셋에 저장해 중복을 제거했다.
			인덱스를 얻어야하므로 리스트에 옮기고, 문제 조건에 따라 정렬해준다.
		*/
		for(String a : set) {
			list.add(a);
		}
		Collections.sort(list);

		
		/*
			record 리스트에는 부분문자열의 조합에 대한 모든 경우의 수가 담겨있다.
			하나씩 꺼내어 최대값을 찾으면 된다.
		*/
		int maxValue = 0;
		for(String[] a : record) {
			if(list.indexOf(a[0]) + list.indexOf(a[1]) + list.indexOf(a[2]) + 3 > maxValue) {
				maxValue = list.indexOf(a[0]) + list.indexOf(a[1]) + list.indexOf(a[2]) + 3;
			}
		}
		
		bw.write(Integer.toString(maxValue));
		bw.flush();
		bw.close();
	}
}