[백준] 5904번 Moo 게임 (Python)

정답 코드 및 풀이는 맨 아래에 있습니다.

https://www.acmicpc.net/problem/5904

• 구상하기에 좀 어려웠다. 다른 풀이법 참고 하여 구상을 하였더니, 어렵지 않게 구현에 성공하였다.

---

< Moo  게임> 

[문제]

Moo는 술자리에서 즐겁게 할 수 있는 게임이다. 이 게임은 Moo수열을 각 사람이 하나씩 순서대로 외치면 되는 게임이다.

Moo 수열은 길이가 무한대이며, 다음과 같이 생겼다. 

m o o m o o o m o o m o o o o m o o m o o o m o o m o o o o o 

Moo 수열은 다음과 같은 방법으로 재귀적으로 만들 수 있다. 먼저, S(0)을 길이가 3인 수열 "m o o"이라고 하자. 1보다 크거나 같은 모든 k에 대해서, S(k)는 S(k-1)과 o가 k+2개인 수열 "m o ... o" 와 S(k-1)을 합쳐서 만들 수 있다.

S(0) = "m o o"
S(1) = "m o o m o o o m o o"
S(2) = "m o o m o o o m o o m o o o o m o o m o o o m o o"

위와 같은 식으로 만들면, 길이가 무한대인 문자열을 만들 수 있으며, 그 수열을 Moo 수열이라고 한다.

N이 주어졌을 때, Moo 수열의 N번째 글자를 구하는 프로그램을 작성하시오.

[입력]

첫째 줄에 N (1 ≤ N ≤ 10^9)이 주어진다.

[출력]

N번째 글자를 출력한다.

예제 입력	예제 출력
11	m

---

틀린 아이디어

이전 문자열과 더할 문자열의 길이를 파라미터로 주어 길이가 n보다 클 때까지 반복하여 재귀함수를 호출한다. 길이가 조건에 만족되면 이전 문자열 + "mo...o" + 이전 문자열을 리턴한다. 그 문자열의 n - 1번 인덱스를 프린트한다.

틀린 코드와 틀린 이유

n = int(input())
def recGetNthChar(s, add_str_len):
    if len(s) * 2 + add_str_len >= n:
        return s + 'm' + 'o' * (add_str_len - 1) + s
    return recGetNthChar(s + 'm' + 'o' * (add_str_len - 1) + s, add_str_len + 1)
print(recGetNthChar("moo", 4)[n - 1])

기능상으로는 완벽한 코드이다. 하지만 메모리 제한때문에 이 코드는 통과할 수 없었다. N이 10^9이라면 문자열의 길이가 적어도 10^9개이고, 10^9Byte = 1GB가 필요하다. 128MB로는 택도 없었다.

새로운 아이디어

재귀함수의 파라미터로는 인덱스와, 수열의 길이만 넣어주어야 한다는 것을 알았다. 최대한 작은 것으로 줄였을 때 문자를 리턴해주면 되는 것이었다. 먼저 길이가 n보다는 크거나 같은 수열의 바로 직전 수열에 대한 정보를 구한다.(직전 수열의 길이와, 직전 수열에서의 더할 수열의 길이) 그 후, 직전수열길이, 더할수열길이, 위치를 이용하여 재귀함수를 이용해 문자를 리턴한다.

풀이 및 코드

def recGetChar(prevSeqLen, addSeqLen, location):
    # 종료 조건
    if (1 <= location <= 3):
        return "moo"[location - 1]
    # 위치가 이전 길이보다 작으면 이전 수열(재귀)에서 다시 체크
    if (location <= prevSeqLen):
        addSeqLen -= 1
        prevSeqLen = round((prevSeqLen - addSeqLen) / 2)
        return (recGetChar(prevSeqLen, addSeqLen, location))
    # 위치가 이전 수열 길이 + 1이면 'm'리턴
    elif (location == prevSeqLen + 1):
        return 'm'
    # 이전 수열 + 2 <= loc <= 이전 수열 + 더할 수열 이면 'o'리턴
    elif (location <= prevSeqLen + addSeqLen):
        return 'o'
    # 이전수열 + 더할 수열 < loc이면 loc 조정 후 이전 수열(재귀)에서 다시 체크
    else :
        location -= prevSeqLen + addSeqLen
        addSeqLen -= 1
        prevSeqLen = round((prevSeqLen - addSeqLen) / 2)
        return (recGetChar(prevSeqLen, addSeqLen, location))

def kthStrLen(seqLen, addSeqLen):
    if seqLen * 2 + addSeqLen >= n:
        return seqLen, addSeqLen
    return (kthStrLen(seqLen * 2 + addSeqLen, addSeqLen + 1))

n = int(input())
prevSeqLen, addSeqLen = kthStrLen(3, 4)
print(recGetChar(prevSeqLen, addSeqLen, n))

n이 11이라고 생각해보자. 문자열은 "moo mooo moo moooo moo mooo moo"(공백은 무시)이 된다. 여기서 이전 문자열의 길이는 10이고, n은 이전 문자열 바로 다음 위치이므로 m이 된다. 그리고 n이 만약 12~15이면 비슷한 이유로 o가 된다. 하지만 그 이외의 위치가 될 수도 있다.

n은 prevSeqLen보다 작거나 같을 일이 절대 없지만, 재귀함수를 타는 도중에는 location이 prevSeqLen보다 작아질 수 있다. 그럴 경우에는 재귀함수의 인자로 그전 수열의 정보를 준다. 예를 들어 문자열이 "moo mooo moo moooo moo mooo moo"이고, location이 10이면, 인자 prevSeqLen는 3, addSeqLen은 4, idx는 그대로 10을 넣어주어 더 작은 문자열인 "moo mooo moo"에서 체크하라는 함수를 호출한다.

그 반대로 n이 prevSeqLen + addSeqLen보다 클 경우도 있다. 예를 들어 "moo mooo moo moooo moo mooo moo"문자열에서 location이 16~25인 경우이다. 이런 경우에는 위의 경우와 마찬가지로 그 전 수열인 "moo mooo moo"의 정보와, location을 그 수열에서 적용될 수 있도록 보정해서 인자로 넣어준다. location이 16이었다면 없어진 "moo mooo moo moooo"만큼의 길이인 15를 뺀 1을 인자로 넣어주는 것이다.

중간에 함수가 종료될 수도 있지만 location이 1~3이 되면 더 작은 수열로 갈 수 없으므로 종료조건으로 넣어주었다.

후기

문제를 풀기 전에는 길이를 먼저 구하는 게 낫지 않을까?라는 생각만 하다가, 길이를 구하면서 문자를 구할 수 있는 함수를 만들 수 있을 줄 알았다. 그것에 꽂혀 결국 구현에 실패하였다. 하지만 다른 사람의 코드를 보고 난 후, '아! 길이를 먼저 구하는 게 맞았네.' 하며 내 구상대로 구현해 볼 것을 후회했다. 나를 더 믿고 한번 더 시도해 보는 습관을 들여야겠다.

추가로 드디어 c언어 계절학기와 42서울 libft 과제가 끝났다. 오랜만에 알고리즘 공부하니까 혈액순환이 활발해지는 기분이다 ~! 이때동안 소홀했던 알고리즘에 더 몰입하는 시간을 갖도록 하겠다.