[구름톤 챌린지 2주 차 학습 일기] 6일차 미션 문제 6. 문자열 나누기 (java)

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

구름LEVEL

---

728x90

 

내 생각

저번주에 비해 난이도가 갑자기 휙 뛴 느낌이라 당황했다.

문제에서 해결해야 할 것들은

1. 문자열 3개로 파싱

2. 중복 없이 저장

3. 사전 순으로 정렬

4. 점수 구하기

1번은 2중 for문과 substring()으로 구했고

2번, 3번은 TreeSet으로 해결했다.

4번은 위에서 구한 순서를 다시 Map에 담아 부분문자열이 있으면 순서를 바로 알 수 있게 구현했다.

---

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

class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		String s = br.readLine();
		
		TreeSet<String> ts = new TreeSet<>(); // 문자열을 중복 없이 사전 순으로 담을 자료 구조
		for(int i = 1; i < N - 1; i++) {
			for(int j = i + 1; j < N; j++) {
				ts.add(s.substring(0, i)); // 첫 번째 부분문자열 추가
				ts.add(s.substring(i, j)); // 두 번째 부분문자열 추가
				ts.add(s.substring(j, N)); // 세 번째 부분문자열 추가
			}
		}
		
		// TreeSet에서 순서대로 꺼내며 Map에 부분문자열과 순서 저장
		Map<String, Integer> map = new HashMap<>(); // key := 부분문자열, value := 몇 번째 문자열인지
		int n = 1;
		while(!ts.isEmpty()) {
			map.put(ts.pollFirst(), n++);
		}
	
		// 답 구하기
		int result = 0;
		for(int i = 1; i < N - 1; i++) {
				for(int j = i + 1; j < N; j++) {
					int tmp = 0;
					tmp += map.get(s.substring(0, i));
					tmp += map.get(s.substring(i, j));
					tmp += map.get(s.substring(j, N)); // 점수의 합 구하기
					result = result < tmp ? tmp : result; // 역대 최대값과 비교하여 result 갱신
				}
		}

		System.out.println(result);
	}
}