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

[구름톤챌린지]

문제 # https://level.goorm.io/exam/195688/%EB%AC%B8%EC%9E%90%EC%97%B4-%EB%82%98%EB%88%84%EA%B8%B0/quiz/1

 

 

 

 

 

내가 작성한 코드

import java.io.*;
import java.util.*;

class Case{
	String first, second, third; // 3개의 부분문자열
	
	Case(String first, String second, String third){
		this.first = first;
		this.second = second;
		this.third = third;
	}
}
class Main {
	static int higherScore = Integer.MIN_VALUE; // 가장 높은 점수 저장
	static int N; // 주어진 문자열의 길이 
    static String inputStr; // 주어진 문자열
	static ArrayList<Case> cases = new ArrayList<>(); // 3개의 부분문자열
	static TreeSet<String> treeSet = new TreeSet<>(); // 부분문자열을 중복없이 저장하여 정렬하기 위한 자료구조
	static HashMap<String, Integer> strScore = new HashMap<>(); // 문자열과 점수를 함께 저장하기 위한 자료구조
    static int[] selected; // 부분문자열을 구분하기 위한 조합을 사용할 때 필요한 자료구조

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		inputStr = br.readLine();
		
		selected = new int[N];
		getCase(1, 0); // 부분문자열 경우를 구하여 동적배열에 부분문자열을 저장하고, treeset에 부분문자열을 삽입
		transStr(); // treeset을 사용하여 오름차순으로 정렬된 문자열을 순서대로 점수와 함께 hashmap에 저장
		findMaxScore(); // 동적배열에 삽입된 경우의 수만큼 반복하고, hashmap을 참조하여 최대점수를 구함
		
		System.out.println(higherScore);
	}
	
	static void findMaxScore(){
		for(int i=0; i<cases.size(); ++i){
			higherScore = Math.max(higherScore, getScore(cases.get(i)));
		}
	}
	
	static int getScore(Case c){
		return strScore.get(c.first) + strScore.get(c.second) + strScore.get(c.third);
	}
	
	static void transStr(){ // treeset의 중복없이 오름차순 정렬되는 성질을 이용함 
		int score = 0;
		for(String str:treeSet){
			strScore.put(str, ++score);
		}
	}
    
	static void getCase(int idx, int num){ // 조합을 이용함
    
		if(num == 2){
			String str1 = inputStr.substring(0, selected[0]);
			String str2 = inputStr.substring(selected[0], selected[1]);
			String str3 = inputStr.substring(selected[1], N);
			cases.add(new Case(str1, str2, str3));
			treeSet.add(str1);
			treeSet.add(str2);
			treeSet.add(str3);
			return;
		}
        
		for(int i=idx; i<N; ++i){
			selected[num] = i;
			getCase(i+1, num+1);
		}
	}
}

 

풀이 및 배운 점

 

처음에 3개의 부분문자열로 나누니까 `0~N-1`중에서 3개의 인덱스를 선택해야한다고 생각했다.

그러나 첫 번째 부분문자열은 0부터 반드시 시작해야하므로 2개의 인덱스만 선택하면 `0~첫 번째 선택한 인덱스-1` `첫 번째 선택한 인덱스 ~ 두 번째 선택한 인덱스-1` `두 번째 선택한 인덱스 ~ N-1` 로 문자열을 고를 수 있음을 뒤늦게 알아차렸다.

 

또 중복없이 문자열을 정렬해야한다는 조건을 고민하면서 자료구조를 찾아보다가 `TreeSet`을 알게되었다.

TreeSet은 이진 검색 트리(Binary Search Tree) 중에서도 레드 블랙 트리로 되어있다고 한다.

 

이 친구에 대해서도 좀 더 공부해봐야겠다.

 

이 친구를 이용하여 부분문자열을 중복없이 오름차순으로 저장할 수 있었다. 

그리고 나타날 수 있는 부문문자열을 모두 저장한 후에, 저장된 크기만큼 반복하여 `<문자열, 반복횟수+1(점수)>` 형태로 저장하여 문자열의 키값을 통해 점수를 알 수 있도록 HashSet을 이용하였다. 

 

마지막으로는 3가지의 부분문자열을 나눌 수 있는 경우가 저장된 동적배열 `cases`의 크기만큼 반복하여 바로 전 단계에서 만들어놓은 HashSet을 통해 해당 케이스의 점수를 구할 수 있었다.

 

 

공부를 하면 할수록 알아야 할 것이 많고 배우고 싶은 것들이 정말 많은 것 같다.