[WEEK02] 백준 2주차 퀴즈 - 분할정복 / 스택 / 우선순위 큐

1. 5904번 : Moo 게임

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

처음 제출한 코드는 아래와 같다.

import sys
input = sys.stdin.readline

def recur(n):
    if n == 0:
        return "moo"
    
    return recur(n-1) + "m" + "o" * (n+2) + recur(n-1)

N = int(input())
result = recur(N)   # 재귀로 돌려서, N자리를 포함하는 문자열을 얻어낸다. 
print(result[N-1])  # N번째 문자를 뽑는다.

S(1) = moo
S(2) = S(1) + mooo + S(1) = moo mooo moo
S(3) = S(2) + moooo + S(2) = moo mooo moo moooo moo mooo moo

.. 쭉 써보면서 규칙을 발견할 수 있었고, 이를 임의의 재귀를 만들어 접근해 보았다.

recur(0) = m + oo
recur(1) = recur(0) + m + ooo + recur(0)
recur(2) = recur(1) + m + oooo + recur(1)

하지만, 런타임에러가 떴다.

파이썬은 재귀의 최대 깊이가 1000까지라고 한다. 따라서, 재귀를 다루는 문제는 반드시 sys.setrecursionlimit(10**6) 을 넣어줌으로써 범위를 늘려야 한다.

위 코드만 넣고, 다시 돌려 봤으나..! 이번엔 메모리초과가 떴다.
듣고 보니 result[]라는 리스트에 담아 접근하고자 했던 게 문제였다..
즉, 내가 짠 코드에서 "틀렸습니다"가 나올 수밖에 없는 이유로 다음과 같이 분석했다.

• 입력 받은 N을 recur(N)으로 넘기면, 재귀를 너무 많이 호출하게 된다. (n번째만 찾고 싶은데, n의 범위를 훨씬 넘어서서 재귀를 비효율적으로 사용한다.)
• 리스트에 다 담아서, N을 접근하기에는 result가 비효율적으로 너무 뚱뚱하다. (비효율적인 메모리 사용이다.)
• 음..다 뜯어 고쳐야 하나..?

앞선 문제를 어떻게 접근해야 했고, 이를 코드로 어떻게 적용했는지 기록해 보겠다.

런타임 에러 발생 이유

⇒ 파이썬에서 재귀를 사용하는 문제는 반드시 sys.setrecursionlimit(10**6)을 넣어주어야 한다. (파이썬에서 재귀의 최대 깊이가 1000까지이기 때문)

알고리즘 : N번째 문자 출력하기
Input : N
Output : N번째 문자

moo 순열은 전체적으로 S(k) = S(k-1) + m + o * (k + 2) + S(k-1)의 규칙을 갖는다.

점화식으로 풀어보고자 다음과 같이 시도해 봤다..
음..위의 시도와 상관 없이 쉽게 접근해 보자면, (참고한 레퍼런스는 https://tesseractjh.tistory.com/101)

입력 받은 N에 대하여, N이 위치할 수 있는 부분을 크게 세 가지로 구분할 수 있다.

• 왼쪽 → S(k-1)
• 중간 → m + o * (k+2)
• 오른쪽 → S(k-1)

이에 앞서, 왼쪽/중간/오른쪽 그 어느쪽이든 위치하기 위해서는 우선 문자열이 N보다는 길어야 한다.

그리고 나서, 해당 문자열의 중간 지점을 두고 N이 왼쪽에 있는지, 오른쪽에 있는지 아니면 중간에 있는지를 재귀로 검사해서 문자를 유추한다.

즉, “쪼개서 살펴보자!” 하는 분할정복으로 문제를 접근해야 한다.

다시 정리하자면, Moo의 풀이 로직은 다음과 같다.

1) N보다 큰 크기를 구한다. (이때 앞서 살펴본 점화식을 이용하여, 해당 규칙을 유지하는 문자열의 길이를 산출한다.)
2) 재귀를 통해, 전체 (임시) 문자열에서 N의 위치를 파악하고
3) 해당 위치에서의 문자를 찾는다.

근데 또 다시 메모리 초과가 난다.. (PyPy 대신 Python으로 돌려야 한다! PyPy가 Python보다 빠른 대신, 메모리 용량이 작기 때문이다.)

import sys
sys.setrecursionlimit(10**6 )
input = sys.stdin.readline

def moo(acc, ctr, N):   # ctr은 중간 지점의 길이이다.
    prev = (acc-ctr) // 2
    if N <= prev: return moo(prev, ctr-1, N)
    elif N > prev + ctr: return moo(prev, ctr-1, N-prev-ctr)
    else: return "o" if N-prev-1 else "m"

N = int(input())

acc, n = 3, 0   # acc는 m과 o로 이루어진 전체 문자열의 길이이고, n은 점화식에서 k의 역할과 같다고 상정한다.
while N > acc:
    n += 1      # 점화식에서 k이다!
    acc = acc*2 + n+3

result = moo(acc, n + 3, N)
print(result)

---

2. 16120번 : PPAP

백준 : https://www.acmicpc.net/problem/16120

제출한 코드는 다음과 같다.

# PPAP 스택의 로직은 계산기 할 때와 비슷하다. => 문제 잘못 이해함!!!

# (아래 로직 틀림 -> 코드 옆에 주석으로 수정함!)
# 1. 입력 값이 P인 경우
# 1) 스택이 비어있다면 -> push
# 2) 스택이 비어있지 않다면 -> 스택의 맨 위 원소를 확인해서
#   1) P인 경우 -> push
#   2) A인 경우 -> pop 하고 -> P 자신을 answer에 갖다 붙힌다. => 정답이 되므로 break 한다!!

# 2. 입력 값이 A인 경우
# 1) 스택이 비어있다면 -> 그냥 버리기
# 2) 스택이 비어있지 않다면 -> 스택 맨 위 원소를 확인해서
#   1) P인 경우 -> pop 한다(answer 붙이기) -> 한 번 더 pop 했을 때
#       1) P인 경우 pop 하고 answer에 붙인 후 -> A를 push 한다. => 1. 2) 2)으로 연결 된다.
#   2) A인 경우 -> pop 하고 -> A 그냥 버린다.

# 마지막에 answer가 PPAP라면 PPAP를 출력하고 / 아니라면 NP를 출력한다.

import sys
input = sys.stdin.readline

stack = []

str = input().strip()
answer = ""

n = len(str)
for i in range(n):
    if str[i] == 'P':
        if not stack or stack[-1] == 'P': # 스택이 비어 있거나 / 맨 위의 요소가 'P'라면
            stack.append(str[i])          # => push 한다.
            continue
                
        answer += stack.pop()             # 'A'인 경우 => pop 하고 P 자신을 answer에 갖다 붙힌 후 -> ★ break 한다!
        answer += str[i]
        # print(stack)
        break

    else: #str[i] == 'A' 
        if not stack:                   # 스택이 비어있다면
            continue                    # => 그냥 버린다.
        
        if stack[-1] == 'A':            # 스택의 top이 A라면 이전 것도, 지금 것도 버린다.
            stack.pop()
            continue

        while stack:                    # (P라면) 스택의 모든 요소를 pop 한다. (스택에는 P만 쌓여있을 것)
            top = stack.pop()          
            answer += top
        
        stack.append(str[i])        # => 그리고 나서 A를 push 한다. => ★ 다음이 P라면 끝난다!
        if answer == 'P':              
            answer = ""

if answer == 'PPAP': 
    print('PPAP')
else:
    print('NP')

두 차례나 "틀렸습니다"가 뜬 이유는,,문제를 두 번이나 잘못 이해했기 때문이다.
(앞으로는 문제 조건을 제대로 확인하자,,)

정상적인 PPAP의 슈도 코드는 다음과 같다.

if 'P' or 'PPAP' then print(PPAP) # 1. P 혹은 PPAP는 'PPAP'이다.
else
- for i in word # 입력받은 문자열 하나씩 확인
-- stack.append(i)
-- if stack[-4:] == ppap then stack.pop() * 3
- if stack is ppap or p then print(PPAP) # 2. stack에 PPAP 혹은 P만 남은 경우 'PPAP'
- else print(NP) # 3. 1과 2가 안 된다면 'NP'이다.

import sys
input = sys.stdin.readline
word = input().rstrip()

if word == 'P' or word == 'PPAP':
    print('PPAP')
else:
    stack = []
    ppap = ['P', 'P', 'A', 'P']
    for i in word:
        stack.append(i)
        if stack[-4:] == ppap:
            stack.pop()
            stack.pop()
            stack.pop()

        if stack == ppap or stack == ['P']:
            print('PPAP')
        else:
            print('NP')

---

3. 1933번 : 스카이라인

백준 : https://www.acmicpc.net/problem/1933

제 시간 내에 못 풀었지만, 조만간 풀어서 올리겠다.