[Goorm/Python] 문자열 나누기 || 구름톤 챌린지

구름톤 챌린지 문자열 나누기 195688 파이썬

구름LEVEL

❍ 문제

길이가 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는 알파벳 소문자로만 구성되어 있다.

❍ 출력

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

 

❏ 문제 풀이

4개의 문자열을 3개의 부분 문자열로 나누기 위해선 문자열을 {1, 1, 2}, {1, 2, 1}, {2, 1, 1}라는 개수로 각각 나누어야 한다. (ex. {a, b, cd}, {a, bc, d}, {ab, c, d} )
5개인 문자열을 3개의 부분 문자열로 나눌 때에는 {1, 1, 3}, {1, 3, 1}, {3, 1, 1}, {1, 2, 2}, {2, 1, 2}, {2, 2, 1}라는 개수로 각각 나눌 수 있다.
문자의 개수를 보면, 조합이나 순열을 떠올릴 수 있었고, 중복도 가능하므로 중복 순열로 풀이를 해주면 될 것 같았다. 

 

[ 조합 & 순열 구현 방법 정리본 ]

[Algorithm/Python] 파이썬 itertools에서 combinations, permutations를 사용하지 않고, 조합과 순열 구현

 

❍ 중복 순열

import sys
from itertools import product

input = sys.stdin.readline

n = int(input())  # 문자열 길이
arr = input().rstrip()  # 문자열 S

# (1, 1, n - 2)로 가장 큰 수는 n - 2이므로 1부터 n - 1까지로 설정
num = [i for i in range(1, n - 1)]

# 중복 순열
prod = list(product(num, repeat=3))

product는 중복 순열이다. 참고로 순열은 permutations, 조합은 combinations, 중복 조합은 combinations_with_replacement이다.
줄바꿈인 ‘\n’이 포함되므로 rstrip( )을 이용하여 제거해주었다.
 

❍ 합이 n이 되도록

# 중복 순열 중 합이 n인 것만 추출
str_list = []
for x in prod:
    if sum(x) == n:
        i, j, k = x[0], x[1], x[2]
        a = arr[:i]
        b = arr[i : i + j]
        c = arr[i + j :]
        str_list.append((a, b, c))

인덱스 슬라이싱을 이용해주어 n개의 문자열을 i, j, k개의 문자열로 나누어 주었다.
 

❍ 중복을 제거하여 점수계산

# p에 중복 제거하고 담기
p = set()
for a, b, c in str_list:
    p.add(a)
    p.add(b)
    p.add(c)
p = list(p)
p.sort()

# p에서 인덱스 + 1 값으로 result 구하기
result = 0
for a, b, c in str_list:
    a = p.index(a)
    b = p.index(b)
    c = p.index(c)
    result = max(result, a + b + c + 3)

print(result)

 

❍ CODE

import sys
from itertools import product

input = sys.stdin.readline

n = int(input())  # 문자열 길이
arr = input().rstrip()  # 문자열 S

# (1, 1, n - 2)로 가장 큰 수는 n - 2이므로 1부터 n - 1까지로 설정
num = [i for i in range(1, n - 1)]

# 중복 순열
prod = list(product(num, repeat=3))

# 중복 순열 중 합이 n인 것만 추출
str_list = []
for x in prod:
    if sum(x) == n:
        i, j, k = x[0], x[1], x[2]
        a = arr[:i]
        b = arr[i : i + j]
        c = arr[i + j :]
        str_list.append((a, b, c))

# p에 중복 제거하고 담기
p = set()
for a, b, c in str_list:
    p.add(a)
    p.add(b)
    p.add(c)
p = list(p)
p.sort()

# p에서 인덱스 + 1 값으로 result 구하기
result = 0
for a, b, c in str_list:
    a = p.index(a)
    b = p.index(b)
    c = p.index(c)
    result = max(result, a + b + c + 3)

print(result)

 

❍ 조합

다음 날, 해설 코드를 보니, 조합을 이용해주는 방법으로 풀이되어있었다.

중복 순열을 구하고 나서 합이 일치하는 것만 추출해주는 방식은, 중복 순열을 담은 리스트의 값이 매우 커질 수 있기에 불필요한 작업이 될 수 있다.

조합으로 풀이하는 과정은 아래와 같다.

문자열을 3개로 나눌 때, 슬라이싱을 S[ : f], S[f : s], S[ s : ]로 하게 된다.

{a, b, cd}, {a, bc, d}, {ab, c, d}일 때, (f, s)는 각각 (1, 2), (1, 3), (2, 3)이다. 1부터 3까지의 조합을 확인해볼 수 있다.

{a, b, cde}, {a, bc, de}, {a, bcd, e}, {ab, c, de}, {ab, cd, e}, {abc, d, e}일 때, 각각 (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)이다. 1부터 4까지의 조합을 확인해볼 수 있다.

a (1) b (2) c (3) d (4) e 처럼 공백을 2개를 선택하여 문자열 3개로 나눌 수 있다.

import sys
from itertools import combinations

input = sys.stdin.readline

n = int(input())  # 문자열 길이
arr = input().strip()  # 문자열 S

p = set()

# 공백 1부터 n - 1까지
num = [i for i in range(1, n)]
# 조합
combi = list(combinations(num, 2))

 

❍ CODE

import sys
from itertools import combinations

input = sys.stdin.readline

n = int(input())  # 문자열 길이
arr = input().strip()  # 문자열 S

p = set()

num = [i for i in range(1, n)]

combi = list(combinations(num, 2))

for f, s in combi:
    p.add(arr[:f])
    p.add(arr[f:s])
    p.add(arr[s:])

p = sorted(list(p))

result = 0
for f, s in combi:
    temp = 0
    temp += p.index(arr[:f]) + 1
    temp += p.index(arr[f:s]) + 1
    temp += p.index(arr[s:]) + 1
    result = max(result, temp)

print(result)