[Codeforces] CodeCraft-20 - B. String Modification

문제 링크

문제 해석

주어진 문자열을 수정한 결과 중 사전순으로 가장 앞서는 문자열과 그 때의 k값을 출력하는 문제다.
여기서 수정이란, 가장 첫번째 글자부터 k개의 글자를 뒤집고, 두번째 글자부터 k개의 글자를 또 뒤집고, … 이렇게 반복하여 끝까지 뒤집고 나면 문자열을 ‘수정’했다고 한다. 따라서 k는 1부터 문자열의 길이까지 가능하다.

풀이

위에서 말한 ‘수정’하는 함수를 작성해 1부터 n까지의 k값을 주어 실행한 결과를 모두 보면, 아래와 같이 특정한 규칙을 띄는 것을 볼 수 있다.

즉, 문자열 길이가 홀수일 경우, k가 홀수이면 k만큼의 글자를 뒤집어서 뒤에 붙이고 짝수이면 뒤집지 않고 그냥 붙인다. 반대로 문자열 길이가 짝수일 경우, k가 짝수일 때 뒤집어서 붙인다. 이것을 그대로 구현하면 된다!

소스코드

import sys
def input(): return sys.stdin.readline().rstrip()
 
for T in range(int(input())):
    n = int(input())
    s = input()
    ans = s
    k = 1
    for i in range(n):
        s2 = s[i:]
        if n%2 == i%2:
            s2+=s[:i]
        else:
            s2+=s[:i][::-1]
        if s2<ans:
            ans = s2
            k = i + 1
    print(ans)
    print(k)