[벡준] 3954 - Brainf**k 인터프리터

문제 이름 한번 잘 지었네..... f**k만 몇번을 외쳤던가....

A+등급을 딸 때 풀었던 문제라 쉽게생각하고 건드렸다가 문제 출력조건이 조금 달라서 맞왜틀 이러고 1시간을 날려먹은 문제

문제 조건도 애매모호한 부분이 있고, 출력 답의 예시라도 설명을 해줬으면 좋았을 문제....

먼저 출력은 2가지만 생각하면 된다. 정상 종료, loop로 인해 정상종료가 불가능한 경우

정상 종료는 문제가 없는데 loop를 설정하는거에서 문제가 많다....

일단 풀이를 차근히 해보도록 하겠다.

먼저, 이 문제의 핵심은 [, ]일때 점프하는 index를 어떻게 잘 정해주는가이다.

간단히 stack으로 해결할 수 있다.

일단 명령어를 입력받고, 순회하며 stack으로 쌍을 지어 점프 포인트를 만들어 주면 된다.

그 외에는 문제에 대해 충실히 구현만 하면된다 ㅎㅎ

위의 부분까지는 A+취득 할 때 구현했고, 성공했던 부분이라 쉬웠는데 

문제는 loop인데.... 겁나 짜증났던게 loop가 중첩되서 내부의 loop에 갖히는 경우가 있고, 조금 더 외부의 loop에 갖히는 경우가 있다.

문제설명에서 '상위 loop'인지, '내부 loop'인지에 대해 설명만 잘 해줬다면 쉽게 끝났을 문제라고 생각.....

남들 다 이해했다면 내가 머리가 나쁜걸로.....

여기까지 신세한탄하고 차근히 풀이를 써보도록 한다

1. 언제나 그렇듯 입력을 받는다. 하지만 위에서 말한 것과 같이 stack을 사용하여 [, ]의 명령어를 위한 점프포인트를 만들어 준다

2. 단순히 for문을 돌던, while문으로 연산횟수를 count 해주던 하나씩 input으로 넣어서 문제의 조건에 맞게 연산을 해주면 된다.

3. 다만 loop를 설정하기 위해서 max_oper_idx를 선언해 주었는데, 이는 내부 loop가 아닌, 가장 바깥쪽 loop가 답이라는 것을 암시한다

  - 이 부분은 나도 빡쳐서 다른 코드 참고하고 깨닳은 부분이다.....

  - 예를 들어 [+[+-]-]의 경우 내부에 생성된 [, ]쌍이 하나의 무한루프로 보이지만, 실제로 답은 외부의 [, ]라는 뜻이다

  - 이 max_oper_idx는 진행한 명령어의 index의 최댓값을 갱신하며 넣어준다. 그래야 루프가 돌더라도 loop를 찾을 수 있다.

4. 명령어의 index가 명령어의 input 갯수와 같아지면 Terminate, 아니라면 끝까지 돌고 max_oper_idx의 쌍을 출력함으로서 다음 TestCase로 넘어간다.

#include <iostream>
#define MXSIZE 4097
using namespace std;
char oper[MXSIZE], input[MXSIZE];
int stack[MXSIZE], arr[100001], loop[MXSIZE];;
int Sm, Sc, Si;
void PairLoop() {
    int top = -1;
    for (int i = 0; i < Sc; i++) {
        if (oper[i] == '[') {
            stack[++top] = i;
        }
        else if(oper[i] == ']'){
            stack[++top] = i;
            loop[stack[top]] = stack[top - 1];
            loop[stack[top - 1]] = i;
            top -= 2;
        }
    }
}
int main(void) {
    int T;
    cin >> T;
    while (T--) {
        cin >> Sm >> Sc >> Si;
        for (int i = 0; i < Sm; i++) arr[i] = 0;
        for (int j = 0; j < Sc; j++) loop[j] = 0;
        cin >> oper;
        cin >> input;
        PairLoop();
        int idx = 0, oper_idx = 0, input_idx = 0, max_oper_idx = 0;
        bool flag = false;
        for (int i = 1; i <= 50000000; i++) {
            if (oper_idx >= Sc) {
                cout << "Terminates" << endl;
                flag = true;
                break;
            }
            if (oper[oper_idx] == '-') {
                arr[idx] = (arr[idx] - 1) < 0 ? 255 : arr[idx] - 1;
            }
            else if (oper[oper_idx] == '+') {
                arr[idx] = (arr[idx] + 1) % 256;
            }
            else if (oper[oper_idx] == '<') {
                idx = idx - 1 < 0 ? Sm - 1 : idx - 1;
            }
            else if (oper[oper_idx] == '>') {
                idx = (idx + 1) % Sm;
            }
            else if (oper[oper_idx] == '[') {
                if (arr[idx] == 0) {
                    oper_idx = loop[oper_idx];
                }
            }
            else if (oper[oper_idx] == ']') {
                if (arr[idx] != 0) {
                    oper_idx = loop[oper_idx];
                }
            }
            else if (oper[oper_idx] == ',') {
                int c = input_idx >= Si ? 255 : (int)input[input_idx];
                arr[idx] = c;
                input_idx = input_idx >= Si ? input_idx : input_idx + 1;
            }
            oper_idx++;
            max_oper_idx = oper_idx > max_oper_idx ? oper_idx : max_oper_idx;
        }
        if (!flag) {
            cout << "Loops " << loop[max_oper_idx] << " " << max_oper_idx << endl;
        }
    }
    
    return 0;
}