[백준] 13419 탕수육

문제

환규와 태욱이는 둘이서 즐길 수 있는 간단한 게임인 탕수육 게임을 하기로 했다. 게임의 규칙은 다음과 같다.

누가 먼저 시작할지 순서를 정한다.
먼저 시작하는 사람이 단어의 가장 첫 글자를 말한다.
이후 두 사람이 번갈아 가며 자신의 차례에 이전 사람이 말한 글자의 다음 글자를 말한다.
만약 이전 사람이 단어의 가장 마지막 글자를 말했다면 자신의 차례에 단어의 가장 첫 글자를 말한다.
만약 자신의 차례에 잘못된 글자를 말하면 게임에서 지게 된다.
위 규칙을 이용해 탕수육이란 단어를 가지고 게임을 진행하면 다음과 같다.

탕 수 육 탕 수 육 탕 수 육 탕 수 육 …

위 예시에서 밑줄 친 부분은 첫 번째 사람이, 밑줄이 없는 부분은 두 번째 사람이 말하게 되는 부분이다. 이때 밑줄 그어진 부분만 따로 살펴보면 “탕육수탕육수…”가 됨을 알 수 있는데, 따라서 먼저 시작하는 사람은 게임을 시작하기 전에 “탕육수” 만을 기억한 후 상대방이 어떤 단어를 말하든 “탕육수” 순서로 계속 반복해서 말하면 절대로 틀리지 않는다. 만약 “탕육”이나 “탕육수탕”을 기억한다면 기억한 문자열을 처음부터 하나씩 순서대로 말했을 때 자신의 차례에 올바르지 않은 문자를 말하게 되어 게임에서 지게 된다. “탕육수탕육수”를 기억한다고 하더라도 자신의 차례에 틀린 문자를 말하게 되지는 않지만, “탕육수” 만을 기억해도 게임을 진행할 수 있으므로 이 경우 항상 기억해야 할 최소한의 글자만을 기억한다고 가정한다. 또한, 나중에 시작하는 사람도 게임을 시작하기 전에 “수탕육”만을 기억한 다음 “수탕육” 순서대로 반복해서 말하면 절대로 틀리지 않는다.

환규와 태욱이는 이번에는 한글 대신 알파벳을 사용해서 게임을 해보기로 했다. 만약 주어진 단어가 “ABC”이고, 환규가 먼저 시작한다면 환규는 “ACB”를, 태욱이는 “BAC” 만을 기억하면 게임을 지지 않게 된다. 게임에 사용할 알파벳으로 된 문자열이 주어질 때, 두 사람이 미리 기억하고 있어야 되는 문자열 중 가장 짧은 것을 출력하는 프로그램을 작성하시오.

입력

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각각의 테스트 케이스의 첫째 줄에 게임에 사용할 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고 26보다 작거나 같다. 게임에 사용할 문자열은 알파벳 대문자로만 이루어져 있으며 같은 알파벳을 두 개 이상 포함하지 않는다.

출력

출력은 표준 출력을 사용한다. 입력받은 데이터에 대해, 각 테스트 케이스의 답을 순서대로 출력한다. 각 테스트 케이스마다 첫 번째 줄에 먼저 시작한 사람이 기억해야 될 문자열 중 가장 짧은 것을 알파벳 대문자로 출력한다. 두 번째 줄에는 나중에 시작한 사람이 기억해야 될 문자열중 가장 짧은 것을 알파벳 대문자로 출력한다.

내 풀이

import sys
input = sys.stdin.readline

t = int(input())

for _ in range(t):
    game = input()
    if len(game)==1:
        print(game)
        print(game)
    elif len(game)==2:
        print(game[0])
        print(game[1])
    else:     # if len(game)>=3
        if len(game)%2==0:   # even
            print(game[0::2])
            print(game[1::2])
        else:   # odd
            game = game*2
            print(game[0::2])
            print(game[1::2])

처음에는 위의 코드처럼 풀었다가 계속 오답을 받았다.
아래는 다른 풀이를 보고 고쳐서 풀고 정답을 받은 코드 (설명은 코멘트에서)

t = int(input())

for _ in range(t):
    game = input()
    if len(game)%2==0:
        print(game[0::2])
        print(game[1::2])
    else:
        print(game[0::2]+game[1::2])
        print(game[1::2]+game[0::2])

코멘트

이 문제의 관건은 문자열이 홀수의 문자로 이루어져있다면 반복할 규칙을 어떻게 찾냐는 것이었다. 나는 처음에는 홀수의 문자는 2번 반복하면 패턴이 보일 것이므로 그렇게 해서 규칙을 찾으려고 했는데, 그렇게 하면 틀리게 된다. 다른 풀이를 보니 홀수의 문자에서 반복되는 규칙을 간단히 찾았다.
"카카오페이"의 예를 들어주었는데, 이렇게 홀수의 문자에서는 첫 번째 사람은 1, 3, 5, 2, 4번째 문자, 즉 "카오이카페", 두 번째 사람은 2, 4, 1, 3, 5번째 문자, 즉 "카페카오이"처럼 말하게 된다는 것이다.
이를 규칙으로 표현하면 각각 game[0::2]+game[1::2], game[1::2]+game[0::2]가 되는 것이다.
그리고 왜 그런지 모르겠는데 이 문제에서는 import sys input = sys.stdin.readline를 사용하면 무조건 오답처리된다. 이것때문에 오답을 잔뜩 먹었다.....웬만히 헤비해보이는 입력이 아니면 그냥 생략해야겠다.

References

https://www.acmicpc.net/problem/13419
https://kimbangg.tistory.com/18