[구름톤 챌린지 - 9oormthon Challenge] Day 6 문자열 나누기 - Python 파이썬 풀이

 

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

 

📜  문제 

 

 

✏️ 입력 

 

✏️ 출력

 

💡 풀이 

지난주 문제들에 비해 조금 난이도가 있었던 것 같다. 문제 공개 당일까지 풀지는 못하고 다음날 오전에 풀게되었다. 

문자열을 가능한 조합으로 나누고, 그 조합들에서 최대를 찾아야한다.

나는 문자열을 가능한 조합으로 나누는 함수 search를 만들었다. 인자값으로 들어오는 start는 문자열 조합의 시작을 뜻하고 cnt는 남은 문자열을 몇 부분으로 나눌 것인지를 넘겨주도록 했다. global 변수 set을 사용해서 저장하고 중복을 허용하지 않도록 했다.  

cal 함수에서는 문자열 조합들에서 최대값을 계산하도록 했다. start와 cnt는 search 함수와 똑같고, P는 문자열을 임시로 저장하는 배열이다. 

이후 main 에서는 문자열을 입력 받고 함수들을 호출해 나누며 map을 생성해서 내림차순으로 정렬한 후 순서대로 인덱스를 넣어주었다. 

 

 

def search(start, cnt):
    global set  
    if cnt == 0:
        set.add(s[start:])
        return
    for i in range(start + 1, n - cnt + 1):
        set.add(s[start:i])
        search(i, cnt - 1)

def cal(start, cnt):
    global result
    if cnt == 0:
        result = max(result, map[s[start:]] + map[P[1]] + map[P[2]])
        return
    for i in range(start + 1, n - cnt + 1):
        P[cnt] = s[start:i]
        cal(i, cnt - 1)

n = int(input())
s = input().strip()
set = set()
P = [''] * 3
result = -1
map = {}
search(0, 2)
index = 1
for string in sorted(set):
    map[string] = index
    index += 1
cal(0, 2)
print(result)