구름톤 챌린지 2주차 학습 일기 - 3

출처 : 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

 

 

문자열 나누기 문제이다.길이가 N인 문자열 S가 주어진다. 문자열 S를 서로 겹치지 않는 3개의 부분문자열로 나눈다. 부분문자열은 모두 길이가 1 이상이여야 하며, 원래 문자열에서 연속해야 한다. 

 

조건 1. 문자열 S를 위 조건에 따라 나눴을 때, 등장하는 모든 부분문자열을 중복 제거하고 사전순으로 정렬한 결과를 P라고 한다.

 

조건 2. 나누어진 3개의 문자열이 각각 P에서 i,j,k번쨰로 등장하는 문자열이라면, 얻을 수 있는 점수는 i+j+k이다.

 

예를 들어, abcd 라는 문자열을 부분문자열을 중복 제거하고 사전 순서로 정렬한 결과 P는 a, ab, b, bc, c, cd, d이다. 이때 {ab, c, d}로 문자열을 나눈 경우 얻을 수 있는 점수는 2 + 5 + 7 = 14점이고, 얻을 수 있는 최대 점수이다.

 

 

 

순서가 없고 중복이 없는 방법! 조합이 떠올라야 한다. 여기서 문자열들을 어떤 방법으로 나눌 것이냐를 생각해봐야 하는데 문자열의 길이가 최대 100이기 때문에 완전 탐색으로 접근할 수 있다. 그리고 3개의 문자열로 나누려면 문자열 사이의 2개의 공백을 두고 나눠야 한다. 아래 그림과 같이 문자열 사이 공백에 숫자를 순서대로 나열해서 두 수를 기준으로 나누면 부분문자열 3개를 만들 수 있다. 

 

1. 문자열의 길이가 5라면 문자열의 각 문자 사이에 4개의 공백이 들어갈 수 있다.

blank = [i for i in range(1,N)]

2. 부분 문자열을 담을 set()을 선언한다.

P = set()

3. 공백 2개를 선택한 조합의 배열을 저장해둔다.

comb = list(itertools.combinations(blank, 2))

4. comb 배열의 각 원소를 꺼내 P에 저장해준다. 

for f, s in comb :
    p.add(S[:f])
    p.add(S[f:s])
    p.add(S[s:])
    

P = list(P)
P.sort() # 사전순 정렬

5. 쪼갠 문자열의 조합 순서대로 점수를 구한 후 res 변수에 최대값을 갱신해준다.

for f,s in comb :
    temp = 0
    
    temp = P.index(S[:f]) + 1
    temp = P.index(S[f:s]) + 1
    temp = P.index(S[s:] + 1
    
    res = max(res, temp)

print(res)

 

 

정해 코드 :

from itertools import combinations

N = int(input())
S = input()

P = set()

blank = [i for i in range(1, N)]
comb = list(combinations(blank, 2))

for f, s in comb:
	P.add(S[:f])
	P.add(S[f:s])
	P.add(S[s:])

P = sorted(list(P))

result = 0

for f, s in comb:
	temp = 0
	
	temp += P.index(S[:f]) + 1
	temp += P.index(S[f:s]) + 1
	temp += P.index(S[s:]) + 1
	
	result = max(result, temp)

print(result)

 

파이썬을 사용할 경우, itertools.combinations를 사용하여 간단하게 구현이 가능하지만 JAVA에선 반복문으로 일일이 구해주어야 한다. 구현이 어렵진 않은 것 같지만 번거롭다고 느꼈다... 

import java.util.*;

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

        int N = scanner.nextInt(); 
        scanner.nextLine(); // to consume newline left by nextInt()
        String Word = scanner.nextLine();

        List<String[]> wordList = new ArrayList<>();
        Set<String> Score = new HashSet<>();

        // 위치를 2개 정하는 모든 조합 구하기
        for (int i = 1; i < N; i++) {
            for (int j = i + 1; j < N; j++) {
                String first = Word.substring(0, i);
                String second = Word.substring(i, j);
                String third = Word.substring(j);
                wordList.add(new String[]{first, second, third});
                Score.add(first);
                Score.add(second);
                Score.add(third);
            }
        }

        List<String> tempScoreList = new ArrayList<>(Score);
        Collections.sort(tempScoreList);

        Map<String, Integer> wordScore = new HashMap<>();
        for (int i = 0; i < tempScoreList.size(); i++) {
            wordScore.put(tempScoreList.get(i), i + 1);
        }

        int maxScore = -1;
        for (String[] words : wordList) {
            int tempScore = 0;
            for (String word : words) {
                tempScore += wordScore.get(word);
            }
            maxScore = Math.max(maxScore, tempScore);
        }
        
        System.out.println(maxScore);
    }
}