9519. 졸려

문제의 내용이 궁금하시다면, 아래의 링크를 클릭해주세요!
문제 보러 가기

접근 과정

나름 난해했던 조건

단어의 뒷 부분 절반이 앞 부분과 섞인다는 점을 처음에 정확히 이해하지 못해 시간이 걸렸다.

• 마지막 글자는 첫 글자와 두 번째 글자 사이로 이동한다.
• 뒤에서 2번째 글자는 두 번째 글자와 3번째 글자 사이로 이동한다.
• ...
• 뒤에서 k번째 글자는, k번째 글자와 k + 1번째 글자 사이로 이동한다.

원본 단어의 앞 부분과 뒷 부분을 분리하는 부분까지는 문제가 없었지만, 위의 조건을 잘못 이해해서 아래와 같은 흐름을 생각했다.

abcdef -> abc (앞) / def (뒤) 
# 마지막 글자 -> 1번과 2번 사이로
abcdef -> f (마지막 글자) -> afbcde
afbcde -> e (뒤에서 2번째) -> afebcd
afebcd -> d (뒤에서 3번째) -> afedbc

k번째 글자와 k + 1번째 글자.. 를 포함하는 문자열의 대상을, 전체 문자열 X로 잡았던게 오해를 불러온 원인이었다.

하지만, 실제 대상이 되는 문자열은 문자열의 앞 부분이다.
k번째 글자, k + 1번째 글자는 문자열의 앞 부분을 기준으로 해야 한다!
따라서 흐름을 올바르게 바꾸어보자면 아래와 같다.

abcdef -> abc (앞) / def (뒤) 
# 마지막 글자 -> 문자열 앞 부분 abc의 1번과 2번 사이로
abc -> f -> afbc
# 뒤에서 2번째 글자 -> 문자열 앞 부분 abc의 2번과 3번 사이로
afbc -> e -> afbec
# 뒤에서 3번째 글자 -> 문자열 앞 부분 abc의 3번과 4번 사이로
# 다만 문자열 앞 부분의 길이는 3이기 때문에, 이 경우 가장 뒤 문자인 c의 다음에 위치하게 되는 듯하다.
afbec -> d -> afbecd

이렇게 문자열 앞 부분 abc의 각 단어 사이에 뒷 부분의 단어를 뒤에서부터 삽입해서, 한 번 눈을 깜빡이고 나면 어떻게 변화하게 되는지 알 수 있게 된다!

필요한 건, 앞이 아닌 뒤로 되돌리는 것

하지만 문제에서 요구하는 출력 조건은 N번 깜빡이기 전의 문자이다.
위에서 떠올린 눈을 깜빡이고 난 이후의 조건을 되돌려서, 깜빡이기 전의 문자를 만들어야 한다!

변화된 문자열을 다시 되돌리려면, 우선 문자열 내 문자를 홀수와 짝수를 기준으로 나누어야 한다.
왜 그럴까?
변화된 문자열은, 원본 문자열의 뒷 부분이 앞 부분 사이사이에 끼어든 형태이기 때문이다.

이렇게 홀수와 짝수 기준으로 나누면, 홀수 번째 문자는 원본 문자열의 앞 부분, 짝수 번째 문자는 원본 문자열의 뒷 부분을 뒤집은 모양이라는 것을 알 수 있다!

왜 뒤집은 모양이 되는걸까?
그 이유는 문자열을 섞을 때, 마지막 문자부터 사용하기 때문이다.

변화된 문자열에서 짝수 번째 문자 리스트에 홀수 번째 문자 리스트를 다시 뒤집어서 더하면, 변화되기 전의 문자열을 만들 수 있다!

# 눈을 깜빡여서 변하게 된 문자열 afbecd을 다시 되돌리려면?
# 문자열 내 문자를 홀수와 짝수 기준으로 나누어보자.
odd_word = ['a', 'b', 'c']
even_word = ['f', 'e', 'd']

# 짝수 번째 문자 리스트를 뒤집고, 이를 홀수 번째 문자 리스트에 더한다.
['a', 'b', 'c'] + ['d', 'e', 'f'] -> 'abcdef'

주어진 횟수 N번만큼 전부 수행해야 할까?

문제에서 제시하는 횟수 N의 최댓값은 10억이다.
당연히 이 횟수만큼 정직하게 연산을 수행하면, 시간 제한 내에 문제를 풀 수가 없다!

이 정도 숫자를 보게 되면, 주어진 횟수 N을 줄일 수 있는 규칙이 있을 것이다라는 추측을 할 수 있다.
어떻게 주어진 횟수 N를 줄일 수 있을까?

문자열을 되돌리는 연산을 계속 수행하다 보면, 어느 순간 되돌리고 난 문자열이 처음에 주어졌던 문자열 X와 동일해지는 순간이 오게 된다!

특정 횟수 a를 기준으로 문자열이 다시 처음과 동일해진다는 것은, a회를 주기로 문자열이 처음과 동일해짐을 의미한다.
이를 통해, 문제에서 주어지는 횟수 N이 아무리 크더라도 N % a번만 문자열을 되돌리는 작업을 수행하면 된다는 것을 알 수 있다!

정리하면...

• 문자열의 뒷 부분을, 뒤에서부터 문자열의 앞 부분에 삽입한다.
• 문자열을 되돌리려면?
  • 되돌리려는 문자열을 홀수 번째와 짝수 번째 문자로 나눈다.
  • 짝수 번째 문자 리스트에, 홀수 번째 문자 리스트를 뒤집어서 더해준다.
• 되돌린 문자열이 문제에서 제시한 문자열과 동일해지는 횟수 A를 찾는다.
  • 그 후, N % A 회만큼 문자열을 되돌리는 연산을 진행한다.

풀이

def backword(word):
    global loop
    odd_word = []
    even_word = []
    for i in range(len(word)):
        if i % 2: odd_word.append(word[i])
        else: even_word.append(word[i])
    backward_word = even_word + odd_word[::-1]
    loop += 1
    return ''.join(backward_word)


N = int(input())
X = input()
clone = X[:]
loop = 0

for _ in range(N):
    clone = backword(clone)
    if clone == X:
        break

new_N = (N % loop)
for i in range(new_N):
    clone = backword(clone)

print(clone)

통과!

읽어주셔서 감사합니다!