Brain F**k 인터프리터
문제 해석
- 배열의 크기, 명령어, 입력이 주어질 때 해당 명령어가 무한루프에 빠지는지 알아내는 문제입니다.
- 각 명령어는 다음과 같이 동작합니다.
- ”-“: 포인터가 가리키는 수를 1 감소시킵니다.
- ”+”: 포인터가 가리키는 수를 2 증가시킵니다.
- ”<”: 포인터를 왼쪽으로 움직입니다.
- ”>”: 포인터를 오른쪽으로 움직입니다.
- ”[”: 만약 포인터가 가리키는 수가 0이면 “[“와 짝을 이루는 “]”로 이동합니다.
- ”]”: 만약 포인터가 가리키는 수가 0이 아니면, “]”와 짝을 이루는 “[“로 이동합니다.
- ”.”: 포인터가 가리키는 수를 출력합니다.
- ”,”: 문자를 하나 읽고 포인터가 가리키는 곳에 저장합니다.
설계(X)
- 아주 어려운 구현문제입니다.
- 구현의 가장 어려운 점은 무한 루프를 찾는 부분입니다.
- 5,6번 명령어를 제외하고는 단순하게 구현하면 됩니다.
- 무한루프를 찾기 위해서 스택 자료구조를 활용합니다.
- 먼저 “[“와 “]”짝을 O(1)에 찾기 위해서 “[“을 스택에 저장후, “]”이 나올경우 jump배열에 해당 짝의 위치를 각각 저장합니다.
- 명령어를 수행하면서, “[” 명령어가 나왔을 때 0이 아닌 경우 스택에 추가해줍니다.
- 만약 0이면 jump배열에 저장된 인덱스로 이동시켜줍니다.
- ”]” 명령어가 나왔을 때, 포인터가 가리키는 수가 0이면 루프를 빠져나온것이므로 스택에 저장된 마지막 값을 제거해줍니다.
- 여기서 중요한 점은 어느 지점이 무한루프인지 찾는 부분입니다.
- 스택에 남아있는 인덱스 중 하나가 무한루프인데, 어느 인덱스가 무한루프인지 그냥 찾기는 어렵습니다.
- 이를 수월하게 하기 위해서, check배열을 이용합니다.
- 만약 “]”명령어에서 루프를 빠져나올 경우, 해당 인덱스를 true체크해줌으로써 무한루프가 아닌 것을 확인할 수 있도록 합니다.
- 5000만번의 명령어를 수행 후, 스택에 남아있는 숫자를 모두 대조하여, check처리가 안된 인덱스를 찾습니다. 바로 그 인덱스가 무한루프의 시작점이 됩니다.
- 미리 구한 jump배열을 통해서 시작점의 짝인 끝점을 구할 수 있습니다.
구현(X)
코드
#include <iostream>
#include <cstring>
#include <stack>
using namespace std;
#define MAXN 100000
int N,M,I;
stack<int> st;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--){
while (!st.empty()) st.pop();
int arr[MAXN]={0,};
int jump[4100]={0,};
bool check[4100] = {false,};
cin >> N >> M >> I;
string order,tmp;
cin >> order >> tmp;
for (int i = 0 ;i < M; i++){
if (order[i] =='['){
st.push(i);
}
else if (order[i] ==']'){
jump[st.top()] = i;
jump[i] = st.top();
st.pop();
}
}
while (!st.empty()) st.pop();
int time = 0;
int idx = 0;
int p_idx = 0;
bool flag = false;
int str_idx = 0;
while (time < 50000000){
if (idx >=M) {
flag = true;
break;
}
if (order[idx] == '+') arr[p_idx] = (arr[p_idx]+1)%(1<<8);
else if (order[idx] == '-') arr[p_idx] = (arr[p_idx]+255)%(1<<8);
else if (order[idx] == '<') p_idx = (p_idx + N -1) % N;
else if (order[idx] == '>') p_idx = (p_idx+1)%N;
else if (order[idx] == ','){
if (str_idx< tmp.length()){
arr[p_idx] = tmp[str_idx++];
}
else arr[p_idx] = 255;
}
else if (order[idx] == '['){
if (arr[p_idx]==0){
idx = jump[idx];
}
else{
st.push(idx);
}
}
else if (order[idx] == ']'){
if (arr[p_idx]!=0){
idx = jump[idx];
}
else{
check[idx] = true;
st.pop();
}
}
idx++;
time++;
}
if (!flag) {
while(!st.empty()){
if (!check[jump[st.top()]]) {
printf("Loops %d %d\n",st.top(),jump[st.top()]);
break;
}
st.pop();
}
}
else printf("Terminates\n");
}
return 0;
}
디버깅
- 처음에 8번 명령어가 별 중요한 부분이 아닌 줄 알고 구현을 하지 않았습니다.
- 주어진 샘플입력 중 마지막 명령어를 수행할 때, 8번 명령어가 무시되어 잘못된 값을 출력하는 것을 깨닫고 추가 구현하였습니다.
제출결과
- 1288ms
마무리
- 아주 어려운 구현문제였습니다. 삼성 A형테스트 기출문제에서 가장 어려운 문제였던 것 같습니다.