[구름톤 챌린지] 2주차 6일차 문자열 나누기

 

 

문제

---

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

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

 

 

• 문자열 $S$를 위 조건에 따라 나눴을 때, 등장하는 모든 부분문자열을 중복 제거하고 사전순으로 정렬한 결과를 $P$라고 한다.
• 나누어진 $3$개의 문자열이 각각 $P$에서 $i, j, k$번째로 등장하는 문자열이라면, 얻을 수 있는 점수는 $i+j+k$이다.

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

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

입력

---

첫째 줄에 문자열의 길이 정수 $N$이 주어진다.
둘째 줄에 문자열 $S$가 주어진다.

• $3 \leq N \leq 100$
• $S$는 알파벳 소문자로만 구성되어 있다.

출력

---

문자열을 나눠서 얻을 수 있는 최대 점수를 출력한다.

 

---

문제 접근 방식

---

파이썬에는 itertools라는 아주 좋은 모듈이 있다.

 

원래대로라면 모든 경우의 수의 조합을 구할 때 백트래킹이나 for문 같은 걸로 이끌어내곤 한다.

 

이 문제의 경우, 문자열이 $3$부분으로 분리가 되므로 분리점이 되는 인덱스를 $2$개를 뽑아서 이를 통해 구현해주면 된다.

 

따라서, 이중 for문으로 구현해도 좋고, itertools의 combinations함수를 통해 인덱스를 2개 뽑아서 직접 구현해도 된다.

 

이렇게 인덱스를 뽑아서 문자열을 분리하고 나면, 그 부분 문자열들을 set에 담아주어 중복을 제거한다.

 

모든 부분 문자열들이 모인다면, 이를 sorted함수를 통해 정렬해주면 된다.

 

이후 다시 모든 조합들을 따져보며 최대 점수를 찾아내면 끝이다. 

 

---

정답 코드

---

# 문자열 나누기
import sys
input = sys.stdin.readline
from itertools import combinations

N = int(input())
S = input().rstrip()
string_set = set()
for tpl in combinations(range(1,N), 2):
    sub1, sub2, sub3 = S[:tpl[0]], S[tpl[0]:tpl[1]], S[tpl[1]:]
    string_set.add(sub1)
    string_set.add(sub2)
    string_set.add(sub3)
string_li = sorted(string_set)
max_score = 0
for tpl in combinations(range(1,N), 2):
    sub1, sub2, sub3 = S[:tpl[0]], S[tpl[0]:tpl[1]], S[tpl[1]:]
    score = string_li.index(sub1)+string_li.index(sub2)+string_li.index(sub3)+3
    if score > max_score:
        max_score = score
print(max_score)

 

---

특별히 배운 점

---

해설을 적어보며, 이중 for문이나 백트래킹으로도 구현할 수 있다는 점을 깨달았다.

 

만약 combinations모듈을 쓰기 어려운 형태였다면, 백트래킹으로 접근하는 능력을 길러야겠다.