구름톤 챌린지 2주 차 학습 일기(Day 01)

문제

길이가 인 문자열 가 주어진다. 플레이어는 문자열 를 서로 겹치지 않는 개의 부분문자열로 나누려고 한다. 부분문자열은 모두 길이가 이상이어야 하며, 원래 문자열에서 연속해야 한다.

문자열을 나누는 방법에 따라 플레이어는 점수를 얻을 수 있다. 점수는 다음 과정에 따라 계산된다.

문자열 를 위 조건에 따라 나눴을 때, 등장하는 모든 부분문자열을 중복 제거하고 사전순으로 정렬한 결과를 라고 한다.
나누어진 개의 문자열이 각각 에서 번째로 등장하는 문자열이라면, 얻을 수 있는 점수는 이다.
예를 들어, abcd라는 문자열을 개의 부분문자열로 나누는 방법은 {a, b, cd}, {a, bc, d}, {ab, c, d}의 세 가지가 있다. 여기서 부분문자열을 중복 제거하고 사전 순서로 정렬한 결과는 a, ab, b, bc, c, cd, d이다. 이때 {ab, c, d}로 문자열을 나눈 경우 얻을 수 있는 점수는 점이고, 얻을 수 있는 최대 점수이다.

문자열 를 개의 부분문자열로 나눴을 때 얻을 수 있는 점수 중 최대 점수를 출력하시오.

 

 

 

 

코드

from sys import stdin as s
def backtrack_string(s,start,parts,result):
    if len(parts) > 3:
        return
    
    if start == N:
        if len(parts) == 3:
            result.append(parts[:])
        return
    
    for end in range(start+1,N+1):
        current_part = s[start:end]
        parts.append(current_part)
        backtrack_string(s,end,parts,result)
        parts.pop()
        
        

def split_3_part(s):
    result=[]
    backtrack_string(s,0,[],result)
    return result

if __name__=="__main__":
    N = int(s.readline())
    string = s.readline().strip()
    splits = split_3_part(string)
    ans = []
    
    for split in splits:
        for spli in split:
            ans.append(spli)
            
    answer = sorted(set(ans))
    set_dict_ans = {}
    
    for i,word in enumerate(answer):
        set_dict_ans[word] = i+1
        
    max_score = 0
    for split in splits:
        score=0
        for spli in split:
            score += set_dict_ans[spli]
        max_score= max(max_score,score)
    
    print(max_score)

 

 

느낀점

 

이 문제는 주어진 문자열을 3개의 부분문자열로 나누는 문제입니다. 모든 경우의 수를 다 확인해보고 부분문자열의 수가 3개일 때의 한중 최댓값을 구하는 문제입니다.

 

저는 이 문제를 풀 때 시간이 걸렸던 점과 어려웠던 점은 백트래킹하여 모든 경우의 수를 찾는 것과 반환 값으로 받은 result를 점수계산해서 max_score를 구하는 부분이었습니다.

 

처음에는 단순 반복문을 통해서 max_score를 구하려고 했는데 그렇게하니까 시간 초과가 나와서 통과하지 못했습니다.

해결방법은 어쩌피 index값을 가지고 점수계산을 하는 것이니 dict로 index를 저장하고 있다가 반복문 한 번을 통해 원하는 score값을 찾을 수 있었습니다.

 

완전 탐색 및 dict를 오랜만에 사용해서 구현하는데 시간이 쫌 걸렸지만 백트래킹 알고리즘과 시간 복잡도를 줄이는 dict를 알고 있다면 보다 쉽게 풀어나갈 수 있을 것 같습니다.