[Goormthon] 문자열 나누기

💎 문제링크

구름LEVEL

 

📝 문제

✍🏻 입력 & 출력

🤔 풀기 전에 생각하기

문자열을 앞에서 부터 자르는 문제이기 때문에 바로 substring이 생각이 났다.

나올 수 있는 문자열을 나누어 중복없이 정렬해서 저장하는 문제 TreeSet으로 해결할 수 있다.

문제는 원소를 하나라도 포함하고 있는 3개의 문자열로 어떻게 쪼갤것이냐의 문제이다. 복잡하게 생각했지만 결국 for문의 범위를 잘 설정해줘야 하는 문제였다.

 

문자열이 "abcde" 일 때의 경우

["a", "b", "cde"], ["a", "bc", "de"], ["a", "bcd", "e],

["ab", "c", "de"], ["ab", "cd", "e"],

["abc", "d", "e"]

-> 각각의 문자열 배열을 저장할 List 생성해서 대입

 

Score Set에 들어갈 원소들

["a", "ab", "abc", "b", "bc", "bcd", "c", "cd", "cde", "d", "de", "e"]

-> 각각의 문자열 배열을 생성할 때 Set에도 저장

-> TreeSet으로 만들면 중복제거, 정렬이 같이 된다.

✨ 풀이

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        TreeSet<String> score = new TreeSet<>(); // 점수 목록을 담는 TreeSet 중복 없애고, 사전순 정렬
        ArrayList<String[]> wordList = new ArrayList<>(); // String[] 을 담는 ArrayList 생성

        int N = scanner.nextInt();
        String S = scanner.next();

        for (int i = 1; i < N; i++) { // substring(0, 1)부터 시작해야 제일 처음 문자 저장할 수 있음
            for (int j = i + 1; j < N; j++) {
                String first = S.substring(0, i);
                String second = S.substring(i, j);
                String third = S.substring(j);
                wordList.add(new String[]{first, second, third}); // 만들어지는 조합들 wordList에 저장
                score.add(first); // 점수표에도 저장
                score.add(second);
                score.add(third);

            }
        }

        ArrayList<String> scoreList = new ArrayList<>(score); // 인덱스로 점수계산을 해야하기 때문에 List에 옮겨준다.

        int max = -1;
        for (String[] s : wordList) { // wordList의 문자열 배열들을 하나씩 조회
            int sum = 0;
            for (int i = 0; i < s.length; i++) {
                sum += (scoreList.indexOf(s[i]) + 1); // indexOf를 쓰면 어느 인덱스인지 확인할 수 있음
            }

            max = Math.max(max, sum); // max값을 계속 갱신해서 최대값을 찾음
        }

        System.out.println(max);
    }
}