파이썬으로 풀어보는 백준 3954번: Brainf**k 인터프리터 (삼성 A형 기출 문제)

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

3954번: Brainf**k 인터프리터

 

 

내 풀이:

def go(c):
    global pointer, sm, data_idx, si, code_idx, sc, max_code_idx
    if c == '-':
        arr[pointer] -= 1
        if arr[pointer] == -1:
            arr[pointer] = 255
    elif c == '+':
        arr[pointer] += 1
        if arr[pointer] == 256:
            arr[pointer] = 0
    elif c == '<':
        pointer -= 1
        if pointer == -1:
            pointer = sm-1
    elif c == '>':
        pointer += 1
        if pointer == sm:
            pointer = 0
    elif c == '[':
        if arr[pointer] == 0:
            code_idx = teleport[code_idx]
    elif c == ']':
        if arr[pointer] != 0:
            code_idx = teleport[code_idx]
    elif c == '.':
        pass
    elif c == ',':
        if data_idx < si:
            arr[pointer] = ord(data[data_idx])
            data_idx += 1
        else:
            arr[pointer] = 255
    code_idx += 1
    max_code_idx = max(max_code_idx, code_idx)
 
 
def Loops_check():
    global code_idx, sc, max_code_idx
    cnt = 0
    while code_idx <= sc-1:
        cnt += 1
        go(code[code_idx])
        if cnt >= 50000000:
            print("Loops", teleport[max_code_idx], max_code_idx)
            return
    print("Terminates")
    return
 
cnt = 0
for tc in range(1, int(input()) + 1):
    sm, sc, si = map(int,input().split())
    arr = [0] * sm
    pointer = 0
    code = input()
    code_idx = 0
    data = input()
    data_idx = 0
 
    teleport = [0] * sc
    save = [-1] * (sc//2)
 
    cnt = 0
    for idx, c in enumerate(code):
        if c == '[':
            save[cnt] = idx
            cnt += 1
        elif c == ']':
            cnt -= 1
            teleport[save[cnt]] = idx
            teleport[idx] = save[cnt]
            save[cnt] = -1
    max_code_idx = 0
   Loops_check()

PyPy3, 4264ms

다른 언어에 비해 파이썬으로 풀기에는 매우 불리한 문제였다. 다른 언어에서의 개념이 없다는 전제하에 문제의 설명이 매우 불친절하기 때문이다. modulo 256 이기 때문에 255에서 256으로 넘어가면 0으로 가야 하고 0에서 -1로 가면 255로 넘어가야 한다. 또한 c언어에서는 int형 배열을 만들고 문자를 넣었을 때 아스키코드로 바꿔주는 과정이 필요 없는 것으로 알고 있다. 이 문제를 풀기 위해서는 문자열을 아스키코드로 바꾸는 ord() 함수가 필수적이다. 알고리즘만을 공부한다면 잊어버렸을 수도 있는 함수이다. 또한 무한 루프가 걸렸을 때 출력해야 할 수의 기준이 순환하고 있는 루프가 아닌 처음으로 무한루프를 돌게 만드는 가장 큰 루프이다. 이 부분 역시 설명이 불충분하여 문제를 풀기 쉽지 않았을 것이라 생각한다. 또한 이 문제는 많은 반복문을 순회해야 하기 때문에 python3로는 불가능하다고 판단된다.