3954번: Brainf**k 인터프리터 (데이터 추가, 최신 버전, Python)

문제 링크

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

 

문제 개요

21.01.02 기준 재채점 현황

질문 게시판을 보면 알 수 있지만 문제 설명도 수정되었었고, 테스트 케이스의 빈틈을 노린 코드들이 재채점 되어 글을 작성하는 날 기준으로 solved.ac 랭크 골드 1 임에도 불구하고 맞은 사람 34명, 정답률 9%를 기록하고 있다.

 

다시 말해서 구글 검색을 통해 위 문제에 대한 코드를 올린 블로그는 거의 다 틀린 코드고, 이 때문에 모든 검색 방법을 총동원해서 거의 50번 가까이 제출을 하면서 통과한 문제다.

 

사실 나도 풀고 나서 다시 문제를 보고 있지만 이 지문을 읽고 문제가 요구하는 대로 구현하는 것이 가능한지 잘 모르겠다. 지문이 몇 차례 수정되었다고 하지만 개인적으로 여전히 지문 자체가 모호하다고 생각한다.

---

문제 설명 1

(우선 코드를 작성하기 전에 문제를 계속 읽으면서 문제가 시키는 대로 연습장에 그려보는 것을 추천한다)

문제에서 주어진 테스트 케이스를 통해 설명해보면,

10 4 3 
+-.,
qwe

첫 번째 테스트 케이스다.

길이가 10인 unsigned int 배열을 사용하고, 주어진 명령어의 길이는 4, 입력될 문자열의 길이는 3이다.

다음 줄에 주어진 명령어가 주어지고 그다음 줄에는 입력될 문자열이 주어진다.

 

1000 5 1
+[+-]
a

두 번째 테스트 케이스다.

길이가 1000인 unsigned int 배열을 사용하고, 주어진 명령어의 길이는 5, 입력될 문자열의 길이는 1이다.

다음 줄에 주어진 명령어가 주어지고 그다음 줄에는 입력될 문자열이 주어진다.

 

테스트 케이스마다 주어진 명령어가 5천만(50000000) 번 안에 전부 처리가 될 수 있다면 "Terminates"를, 그렇지 못하다면 무한 루프를 발생시키는 명령어의 괄호 index 값의 쌍을 "Loops X X" 식으로 출력해야 한다.

 

우선 생각해야 할 부분은 unsigned int 배열과, 명령어, 문자열은 전부 독립적이라는 것이다. 8개의 명령어를 보면 다음과 같다.

-	포인터가 가리키는 수를 1 감소시킨다. (modulo 2^8)
+	포인터가 가리키는 수를 1 증가시킨다. (modulo 2^8)
<	포인터를 왼쪽으로 한 칸 움직인다.
>	포인터를 오른쪽으로 한 칸 움직인다.
[	만약 포인터가 가리키는 수가 0이라면, [ 와 짝을 이루는 ] 의 다음 명령으로 점프한다.
]	만약 포인터가 가리키는 수가 0이 아니라면, ] 와 짝을 이루는 [ 의 다음 명령으로 점프한다.
. (온점)	포인터가 가리키는 수를 출력한다.
, (쉼표)	문자 하나를 읽고 포인터가 가리키는 곳에 저장한다. 입력의 마지막(EOF)인 경우에는 255를 저장한다.

 

첫 번째 테스트 케이스를 이용해 초깃값을 세팅하면 다음과 같다.

10 4 3 
+-.,
qwe

-----------------------------------------------------
unsigned int 메모리(배열)
[0,0,0,0,0,0,0,0,0,0]

memory_pointer, command_pointer, string_pointer=0,0,0

두 번째 테스트 케이스를 이용해 초깃값을 세팅하면 다음과 같다.

1000 5 1
+[+-]
a

-----------------------------------------------------
unsigned int 메모리(배열)
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,.........0,0] -> 길이 1000

memory_pointer, command_pointer, string_pointer=0,0,0

주어진 메모리 길이에 맞게 배열을 만들어주고, 조건대로 배열의 값은 0으로 초기화한다. 그리고 메모리, 명령어, 문자열에 각각 pointer를 따로 두어서 주어진 명령어대로 수행하면서 시뮬레이션하면 된다. (말은 쉽지)

 

---

문제 설명 2

명령어에 대해서 처리를 어떻게 해야 할지를 정리해보면 다음과 같다.

    def sol():
        global cp, mp, sp, count
        # 현재 메모리포인터가 가리키고 있는 배열의 값을 -1. +1 해준다
        # 주의할 점은 0에서 -1 하면 255를, 255에서 +1을 하면 0으로 값을 바꿔줘야한다.
        if commands[cp] == "-":
            mem[mp] = (mem[mp] - 1) % pow(2, 8)
        elif commands[cp] == "+":
            mem[mp] = (mem[mp] + 1) % pow(2, 8)
            
            
        # 현재 메모리포인터가 가리키고 있는 위치에서 -1, +1 해준다
        elif commands[cp] == "<":
            mp = (mp - 1) % array_length
        elif commands[cp] == ">":
            mp = (mp + 1) % array_length
        
        
        # 중요한 루프 부분
        # 현재 메모리포인터가 가리키고 있는 배열의 값이 0이면 쌍을 이루는 ] 명령어 위치로 점프를 뛴다
        elif commands[cp] == "[":
            if mem[mp] == 0:
                cp = pair[cp]
        # 현재 메모리포인터가 가리키고 있는 배열의 값이 0이 아니면
        # 쌍을 이루는 [ 명령어 위치로 점프를 뛴다
        elif commands[cp] == "]":
            if mem[mp] != 0:
                cp = pair[cp]
                
                
        # 현재 메모리포인터가 가리키고 있는 배열의 값을 출력한다
        # 이 문제에선 아무것도 해주지 않아도 됨
        elif commands[cp] == ".":
            pass
            
            
            
        # 현재 메모리포인터가 가리키고 있는 배열의 값을
        # 문자열포인터가 가리키고 있는 문자의 아스키값으로 바꿔주고 문자열포인터를 +1 해준다
        # 문자열 포인터가 문자의 끝 EOF 를 가르키고 있는 상태에서 이 명령어가 실행되면
        # 현재 메모리포인터가 가리키고 있는 배열의 값을 255로 바꿔준다.
        elif commands[cp] == ",":
            mem[mp] = input_string[sp]
            if sp < string_length:
                sp += 1
        # 모든 명령어는 수행한 뒤 명령어 포인터를 +1 해준다.
        cp += 1

문제 설명을 보고 이걸 정확히 알 수 있는지에 대한 의문이 든다.

 

조금 더 구체적으로 설명하면 다음과 같다.

1. 모든 명령어는 수행한 뒤 가리키는 위치를 +1 해줘야 한다.

즉 어떤 명령어를 수행하더라도, 심지어 점프를 뛰는 명령어라 하더라도 모든 명령어는 수행 후 다음 명령어를 수행하기 위해 명령어 포인터 값을 +1 해줘야 한다. 위 코드에선 명령어를 수행하고 맨 마지막에 +1 처리를 해주었다.

 

2. +, - 연산 관련해선 unsigned int의 overflow, underflow의 일반적인 방법을 따르면 된다.

이것도 주석에 살짝 언급했지만

0에서 " - " 연산을 할 경우 255,

255 값에서 " + " 연산을 할 경우 0이라는 뜻이다.

문제에선 이렇게 구체적으로 나와있지 않다...

 

3. 문자열 포인터가 문자의 끝까지 갔을 경우에 " , " 명령어가 수행되면 255라는 값을 넣어 줘야 한다.

주어진 문자열이 " abcd "이고 " , " 명령어를 4번 수행해 주어진 문자열을 다 입력한 상태에서 " , " 명령어가 또 들어오면 그 위치에 255를 넣어줘야 한다. 즉 문자열 포인터가 문자의 끝까지 갔을 경우엔 이후에 들어오는 모든 " , " 명령어에 대해서 메모리 포인터가 가리키고 있는 값을 255로 바꿔줘야 한다.

 

4. " [ , ] " 의 쌍은 항상 적합하게 명령어가 들어온다.

[ 와  ]는 루프를 의미하며, 중첩될 수 있다. 입력으로 주어진 프로그램은 잘 짜여 있음이 보장된다. 즉 프로그램을 왼쪽에서 오른쪽으로 훑으면서  [ 의 개수에서  ]의 개수를 빼면 항상 0보다 크거나 같고, 맨 끝까지 훑으면 그 값은 0이 된다.

이 말의 뜻은 명령어에 여는 브라캣 "[ " 이 3개 있다면 닫는 브래킷 "]" 도 3개 있다는 뜻이다.

 

---

문제 설명 3

위에 언급한 1번 테스트 케이스를 시뮬레이션하면 다음과 같다.

1
10 4 3
+-.,
qwe

# 시작
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
count: 0, memory_pointer: 0, command_pointer: 0, string_pointer: 0 

# 1회차
명령어 : +
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
count: 1, memory_pointer: 0, command_pointer: 1, string_pointer: 0 

# 2회차
명령어 : -
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
count: 2, memory_pointer: 0, command_pointer: 2, string_pointer: 0 

# 3회차
명령어 : .
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
count: 3, memory_pointer: 0, command_pointer: 3, string_pointer: 0 

# 4회차
명령어 : ,
[113, 0, 0, 0, 0, 0, 0, 0, 0, 0]
count: 4, memory_pointer: 0, command_pointer: 4, string_pointer: 1 

# command_pointer가 명령어의 길이와 같아졌다 == 명령어를 다 실행했다.
명령어가 전부 수행되었습니다.
Terminates

주어진 명령어를 명령어의 길이인 4까지 전부 수행할 수 있었고 종료된 모습니다.

 

 

2번 테스트 케이스를 시뮬레이션하면 다음과 같다.

1
1000 5 1
+[+-]
a


[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
count: 0, memory_pointer: 0, command_pointer: 0, string_pointer: 0 

명령어 : +
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
count: 1, memory_pointer: 0, command_pointer: 1, string_pointer: 0 

# 반복 시작
명령어 : [
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
count: 2, memory_pointer: 0, command_pointer: 2, string_pointer: 0 

명령어 : +
[2, 0, 0, 0, 0, 0, 0, 0, 0, 0]
count: 3, memory_pointer: 0, command_pointer: 3, string_pointer: 0 

명령어 : -
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
count: 4, memory_pointer: 0, command_pointer: 4, string_pointer: 0 

# 반복 끝, 반복 시작
명령어 : ]
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
count: 5, memory_pointer: 0, command_pointer: 2, string_pointer: 0 

명령어 : +
[2, 0, 0, 0, 0, 0, 0, 0, 0, 0]
count: 6, memory_pointer: 0, command_pointer: 3, string_pointer: 0 

명령어 : -
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
count: 7, memory_pointer: 0, command_pointer: 4, string_pointer: 0 

# 반복 끝, 반복 시작
명령어 : ]
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
count: 8, memory_pointer: 0, command_pointer: 2, string_pointer: 0 

명령어 : +
[2, 0, 0, 0, 0, 0, 0, 0, 0, 0]
count: 9, memory_pointer: 0, command_pointer: 3, string_pointer: 0 

명령어 : -
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
count: 10, memory_pointer: 0, command_pointer: 4, string_pointer: 0 

# 반복 끝, 반복 시작
명령어 : ]
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
count: 11, memory_pointer: 0, command_pointer: 2, string_pointer: 0 


...
...
...

Loops 1 4

명령어를 보면 " [ + - ] " 이 부분으로 인해 무한 루프를 돌고 있다는 것을 알 수 있다. 잘 이해가 안 될 거라고 생각하지만 천천히 콘솔 로그와 명령어를 비교하면서 보면 이 테스트 케이스에 대한 결과를 이해할 수 있을 것이다. 5천만 번까지 작업을 했을 때도 명령어가 끝나지 않았다는 것은 무한루프를 돌고 있다는 것으로 한다고 문제 조건이 말하고 있다.

 

결과적으로 5천만 번까지 돌았음에도 명령어가 끝나지 않아 루프를 돌고 있는 명령어의 인덱스 브래킷 위치인 1과 4를 결과로 출력하고 있다.

 

---

문제 설명 4

여기까지 이해했다면 일단 전체적인 그림은 그려지고 본인이 사용하는 프로그래밍 언어로 구현을 할 수 있을 것이라고 생각한다.

 

위 명령어에서 루프가 만약에 있다면 결국 브래킷에 의해서 발생할 수밖에 없고 루프 중인 브래킷의 인덱스 값을 오름차순으로 출력하면 될 것이다. 브래킷의 위치 쌍은 입력 시에 STACK을 이용해서 pair, hashmap, dict 등 자료구조를 이용해 저장할 수 있다.

 

남은 것은 크게 2가지이다.

 

1. 무엇이 무한 루프인지?

2. 그 무한 루프를 어떻게 구할 것인지

 

1. 무엇이 무한 루프인지?

문제에서 제시하는 무한 루프의 정의는 다음과 같다.

"무한 루프란, 특정 시점부터 탈출하지 않고 무한히 반복 실행되는 루프를 말한다."

즉 탈출도 하지 못하고, 일정한 주기로 무한히 반복되는 루프를 말한다. 

글 읽기 - 무한 루프의 정의를 제안합니다.

위 게시글을 보면 이러이러한 조건으로 인해 무한 루프는 단 하나의 브래킷 쌍만 존재할 수 있다는 것을 알 수 있다.

+ [ [ ] ]  

이런 명령어에서 무한 루프는 1, 4 가 아니라 2, 3이다. 왜냐하면 1, 4는 실제로 탈출하지 못하는 구간이지만 무한히 실행되지도 않기 때문이다.

 

2. 그 무한 루프를 어떻게 구할 것인지

그럼 어떻게 루프의 원인이 되는 브래킷의 위치를 알 수 있을까?

 

데이터가 추가되기 전에 통과했던 풀이들은 다음과 같은 방법으로 해결했다.

 

틀린 방법 1

루프를 돌면서 " [ " 명령어가 수행될 때의 위치를 기억한다. 5천만 번을 돌았을 때의 저장된 위치가 무한 루프를 만드는 브래킷의 위치다.

언뜻 보면 맞는 것 같지만 틀렸다. 반례는 방금 전에 언급한 테스트 케이스다.

 

 

틀린 방법 2

루프를 돌면서 " ] " 명령어가 수행될 때의 위치를 기억한다. 5천만 번을 돌았을 때의 저장된 위치가 무한 루프를 만드는 브래킷의 위치다.

이것 또한 틀린 방법이다. 다음 테스트 케이스를 살펴보자.

++[[++]+]

이 테스트 케이스의 루프는 2, 8이 아니라 3, 6이다.

안쪽의 브래킷은 반복을 하면서 값이 올라가다가 오버플로우가 되어 0이 되는 순간이 온다.(2+2+2+2+2+2+......+2+2=256=0)

즉 안쪽 브래킷을 탈출해 무한 루프의 조건에 위배된다.

 

이 테스트 케이스를 통해서 더 중요한 사실을 한 가지 알 수 있다. 저렇게 무한루프를 도는 것처럼 보이지만 실제로는 탈출을 하는 브래킷이 존재하는데, 5천만 번을 돌고 난 그 순간 안쪽 브래킷의 범위에 명령어 포인터가 위치하고 있다면, 잘못된 무한 루프를 특정하는 셈이 된다.

 

좀 더 풀어서 말하면, 반복문 중에 명령어 포인터가 3~6을 왔다 갔다 하다가 어느 순간 탈출하고 7, 8까지 갔다가 2로 점프를 뛰고 난 뒤 다시 3~6을 왔다 갔다 할 텐데, 위와 같은 방법으로는 정확한 무한 루프의 위치를 알 수 없다.

 

틀린 방법 3

루프를 돌면서 " [ " 명령어가 수행되면 이때 명령어 위치를 stack에 넣어주고,  " ] " 명령어가 수행되면 stack에서 pop을 해준다.
5천만 번을 돌고 스택에 가장 끝에 남아 있는 " [ " 의 위치가 무한 루프를 만드는 브래킷의 위치다.

그럴싸해 보이지만 틀린 방법 1, 2와 구조적으로 다를 게 없다.

 

 

---

문제 설명 5

정리하면, 우리가 찾고자 하는 무한 루프 브래킷의 위치는 무한 루프를 돌고 있는 가장 외곽의 닫는 브래킷을 찾아야 한다.

 

브래킷 안의 브래킷이 무한 루프라면 5천만 번 이후에도 그 안을 돌고 있을 것이고,
브래킷 안의 브래킷이 무한 루프가 아니라면 5천만 번 반복 이후 어느 시점에서 안쪽 브래킷을 탈출해서 실제로 무한루프를 도는 바깥쪽 브래킷으로 접근할 것이다.

이것을 해결하기 위한 방법은 허무할 수도 있지만 5천만 번을 더 반복하는 것이다(...)

 

5천만 번 안에 명령어가 끝나지 않으면 무한루프가 존재하는 것을 알 수 있다. 그 이후에 5천만 번을 더 돌리면 브래킷 안의 브래킷이 위에 테스트 케이스처럼 반복을 하더라도 결국 탈출을 해 실제 무한 루프인 브래킷의 닫는 부분 " ] "에 도달할 것이기 때문이다.

 

Python 코드로는 main이 다음과 같다.

 while cp < command_length:
        count += 1
        # 조건대로 명령어 처리하는 함수
        sol()
        if count >= 50000000:
            break
    # 명령어를 끝까지 실행해서 조기 종료된경우는 끝내면되는데...
    if cp == command_length:
        print("Terminates")
    # 그게 아니여서 5천만번이상을 돌았다면
    else:
        # 한번 더 5천만번을 돌리면서 현재 루프를 돌고 있는,
        # 가장 오른쪽 외곽의 ] 의 위치를 저장한다
        right_end_bracket_index = cp
        while count >= 0:
            count -= 1
            sol()
            right_end_bracket_index = max(right_end_bracket_index, cp)
        # 출력
        print(f"Loops {pair[right_end_bracket_index]} {right_end_bracket_index}")

 

50번에 가까운 제출과, 몇 시간에 걸친 삽질을 했기 때문에 혹시나 이 문제로 고통받고 있는 사람들이 있다면 조금이나마 도움이 되었으면 좋겠다. (물론 노출이 될런가는 모르지만;)