[백준 3954] Brainf**k 인터프리터 (골드1) - 후_후속편

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

 

 

 

본 게시글은 다음 포스팅들의 후_후속편입니다. (도대체 언제까지 실패만 할것인가!)

https://jinn-o.tistory.com/317

[백준 3954] Brainf**k 인터프리터 (골드1)

https://jinn-o.tistory.com/318

[백준 3954] Brainf**k 인터프리터 (골드1) - 후속편

 

 

문제점. 나는 왜?  unsigned 8-bit 정수를 왜 byte 로 관리하고 있었지?

알다시피, byte 자료형은 -128 ~ 127 까지의 범위를 갖는다.

그렇다면 여기서, unsigned, 즉 양수만 해당하는 8-bit 정수라 함은, 0 ~ 255 까지의 범위를 갖는다.

 

그러니까, byte 자료형으로 관리하면, 128 ~ 255 의 범위를 표현할 길이 없는 것이다.

 

왜 나는 갑자기 byte 자료형으로 해야겠다고 생각한거지 ??????????

byte 자료형이 8-bit 의 값을 가진다는 것에 꽂혀서 이상한 실수를 한 것 같다.

 

컴퓨터 전공자 실격이다..

이런 기초적인 실수를 하다니..

 

byte 로 관리하던 데이터 배열의 자료형을 int 로 변환하고, - 나 + 연산시 범위 내에서 순환하도록 수정해주었다.

switch (command) {
    case '-' :
        dataArray[dataIdx] = (curData == 0) ? 255 : (curData - 1);
        break;
    case '+' :
        dataArray[dataIdx] = (curData == 255) ? 0 : (curData + 1);
        break;

	...
    
}

 

 

또 다른 개선사항.

` 프로그램이 명령어를 50,000,000번 이상 수행한 경우, 프로그램은 항상 종료되었거나 무한 루프에 빠져있다. 무한 루프일 경우, 해당 루프는 적어도 한 번 실행이 완료된 상태이며, 한 번의 무한 루프에서 실행되는 명령어의 개수는 50,000,000개 이하이다. `

 

를 믿고, 전체 명령어가 50,000,000 번 이상 수행되면 무한루프로 판명하기로 했다.

 

// excutedCommands 는 50,000,000 에서부터 시작한다.
// 명령어가 시행될때마다 executedCommands 는 하나씩 줄어든다.

if (executedCommands == 0) {
    while (commands[cmdIdx] != '[') {
        cmdIdx --;
    }
    int startIdx = cmdIdx;
    int endIdx = shortCuts[startIdx];

    return LOOPS(startIdx, endIdx);
}

 

현재 무한루프가 발생한 지점에서 가장 최신의 [ 명령어만 찾으면 시작점과 끝점을 연결할 수 있겠지...

 

 

 

..라고 생각했는데.

문제점. 50,000,000 번 수행된 현재 시점에서, 작은 루프가 아니라 큰 루프에서 무한 반복이 시행된 걸 수도 있잖아.

그러니까,

 

가장 안쪽 [] 루프에서 무한 루프를 발견했지만,

(무한루프가 발생하면 가장 최근의 [ 명령어를 찾으므로.)

실은 가장 바깥쪽 [] 루프에서 무한 루프가 돌고 있었을지도 모른다는 것이다.

 

// ★ 현재 실행 중인 `[ ]` 루프 관리
Stack<Integer> loopStack = new Stack<>();

 

그래서 이 루프 스택을 이용해서, [ 명령어가 시행될 때마다 스택에 저장했다.

그리고 ] 명령어로 빠져나갈때마다, 쌓여져 있는 [ 명령어를 제거(pop())했다.

 

그렇게 하고나서, 총 명령어가 50,000,000 번이 돌았을때,

1. stack 이 비었다면 Terminates 를 반환.

2. 비지 않았다면, 가장 큰 [] 루프까지 stack 을 pop 해서 답을 출력한다.

 

 

문제점. 개행 처리.

개행처리에 대해서 StreamBuffer 로 인해 미흡한거같아서 StringBuffer 로 받아서 마지막에 출력하는 방식으로 변경했다.

for (int i=0; i<n; i++) {
    int[] sizes = getIntArr(br.readLine().split(" "));
    int[] dataArray = new int[sizes[0]];
    char[] commands = br.readLine().toCharArray();
    char[] inputs = br.readLine().toCharArray();

    result.append(simulation(dataArray, commands, inputs));
    result.append("\n");
}

// 최종적으로 한 번만 출력
System.out.print(result.toString().trim());

 

 

 

 포기할란다 ..

.... 였는데 뒤에 보면 결국 해결했습니다( 휴)

 

 

 

 

내 마지막 코드 (였던 것)

import java.io.*;
import java.util.*;

class Main {
    static int LOOPS_LIMIT = 50000000;
//    static int LOOPS_LIMIT = 10;
    public static void main(String[] args) throws IOException {
//        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Scanner sc = new Scanner(System.in);
//        StringBuilder result = new StringBuilder(); // 출력 결과를 저장할 StringBuilder
//        int n = Integer.parseInt(br.readLine());
        int n = sc.nextInt();

        for (int i=0; i<n; i++) {
//            int[] sizes = getIntArr(br.readLine().split(" "));
//            int dataArraySize = sizes[0];
//            int commandsSize = sizes[1];
//            int inputsSize = sizes[2];

//            int[] dataArray = new int[dataArraySize];
//            char[] commands = br.readLine().toCharArray();
//            char[] inputs = br.readLine().toCharArray();

            int dataArraySize = sc.nextInt();
            int commandsSize = sc.nextInt();
            int inputsSize = sc.nextInt();

            int[] dataArray = new int[dataArraySize];
            char[] commands = sc.next().toCharArray();
            char[] inputs = sc.next().toCharArray();

//            System.out.println(simulation(dataArray, commands, inputs));
            if (i < n - 2) {
                System.out.print(simulation(dataArray, commands, inputs) + "\n");
            } else {
                System.out.print(simulation(dataArray, commands, inputs)); // 마지막 줄 개행 제거
            }

//            result.append(simulation(dataArray, commands, inputs));
//            result.append("\n");
        }

        // 최종적으로 한 번만 출력
//        System.out.print(result.toString().trim());
    }

    /*
        [예시]
        10 4 3
        +-.,    // commands
        qwe     // inputs
     */
    static String simulation(int[] dataArray, char[] commands, char[] inputs) {

        int[] shortCuts = getShortCuts(commands); // jump 이동시에 사용될 idx map

        // ★ 각 명령어가 몇번 시행됐는지 저장할 배열
        int[] executes = new int[commands.length];

        // ★ 현재 실행 중인 `[ ]` 루프 관리
        Stack<Integer> loopStack = new Stack<>();

        // commands 명령어 배열의 첫 번째 명령, index 0번 부터 시작한다.
        int cmdIdx = 0;
        int dataIdx = 0; // Pointer
        int inputIdx = 0;

        // [종료 조건] 총 시행 명령어가 50,000,000 를 초과함.
        int executedCommands = LOOPS_LIMIT;

        // [종료 조건] commands 배열의 마지막 요소에 접근. -> Terminates 의 경우
        while (cmdIdx < commands.length) {
            if (executedCommands == 0) {
//                while (commands[cmdIdx] != '[') {
//                    cmdIdx --;
//                }
//                int startIdx = cmdIdx;
//                int endIdx = shortCuts[startIdx];
//
//                return LOOPS(startIdx, endIdx);
                while (!loopStack.isEmpty()) {
                    int startIdx = loopStack.pop();
                    if (executes[startIdx] > 0) { // 무한 루프 탐지
                        return LOOPS(startIdx, shortCuts[startIdx]);
                    }
                }
                return TERMINATES();
            }

            char command = commands[cmdIdx];
            int curData = dataArray[dataIdx];
            int curInput = (inputIdx > inputs.length - 1) ? 255 : inputs[inputIdx];

            switch (command) {
                case '-' :
                    dataArray[dataIdx] = (curData == 0) ? 255 : (curData - 1);
                    break;
                case '+' :
                    dataArray[dataIdx] = (curData == 255) ? 0 : (curData + 1);
                    break;
                case '<' :
                    dataIdx = (dataIdx == 0) ? dataArray.length - 1 : dataIdx - 1;
                    break;
                case '>' :
                    dataIdx = (dataIdx == dataArray.length - 1) ? 0 : dataIdx + 1;
                    break;
                case '[' :
                    executes[cmdIdx] ++;
                    loopStack.push(cmdIdx);

                    if (curData == 0) {
                        cmdIdx = shortCuts[cmdIdx];
                    }
                    break;
                case ']' :
                    executes[shortCuts[cmdIdx]] ++;
                    if (curData != 0) {
                        cmdIdx = shortCuts[cmdIdx];
                    } else {
                        loopStack.pop(); // `[ ]` 루프 종료
                    }
                    break;
                case '.' :
                    // 출력한다.
                    break;
                case ',' :
                    dataArray[dataIdx] = curInput;
                    inputIdx ++;
                    break;
            }
            cmdIdx ++;
            executedCommands --;
        }

        return TERMINATES();
    }

    static int[] getShortCuts(char[] commands) {
        int[] shortCuts = new int[commands.length];
        ArrayDeque<Integer> stack = new ArrayDeque<>();

        for (int idx=0; idx<commands.length; idx++) {
            char command = commands[idx];
            if (command == '[')
                stack.push(idx);
            else if (command == ']') {
                int startIdx = stack.pop();
                int endIdx = idx;

                shortCuts[startIdx] = endIdx;
                shortCuts[endIdx] = startIdx;
            }
        }

        return shortCuts;
    }

    static String LOOPS(int startIdx, int endIdx) {
        return "Loops " + startIdx + " " + endIdx;
    }

    static String TERMINATES() {
        return "Terminates";
    }

    static int[] getIntArr(String[] strArr) {
        return Arrays.stream(strArr).mapToInt(Integer::parseInt).toArray();
    }
}

 

 

 

일주일동안 별 시도 다해봤음

 

https://steady-coding.tistory.com/51

[BOJ] 백준 3954번 : Brainf**k 인터프리터 (JAVA)

이 블로그 해답 코드 이해하고 여기다가 다시 이어서 쓸게요

 

너무 힘들게하는 문제네요

 

 

나의 최종 코드

1. shortCuts 배열을 사용해서 각 [ 와 ] 명령어 사이의 짝궁을 저장하는 지름길(?) 배열 생성

public static int[] getShortCut(String commandCode) {
    int cmdSize = commandCode.length();
    int[] result = new int[cmdSize]; // 서로 연결되어있는 괄호의 위치.
    Stack<Integer> stack = new Stack<>();

    for (int i = 0; i < cmdSize; i++) {
        char c = commandCode.charAt(i);

        if (c == '[') {
            stack.push(i);
        } else if (c == ']') { // 닫는 괄호와 여는 괄호를 서로 연결시켜 줌.
            int temp = stack.peek();
            result[i] = temp; // 여는 괄호에는 닫는 괄호의 위치를
            result[temp] = i; // 닫는 괄호에는 여는 괄호의 위치를 저장함.
            stack.pop();
        }
    }

    return result;
}

 

 

2. 총 수행한 명령어의 총합이 50,000,000 이상이 되거나, 그 전이더라도 EOF 에 도달한다면 종료.

 

다만, EOF 에 도달한채로 완료되었다면 그것은 무한 루프가 아니라는 의미이고,

EOF 위치가 아닌 중간 위치라면 무한 루프 안에 있다는 의미일 것이다.

 

이때 무한 루프가 아니라면, 현재 있는 공간이 중첩 반복문인지 파악하는 것이 가장 중요하다.

 

여기선 그 무한루프의 범위를 어떻게 산정했을까?

int pid = 0; // 특정 명령어를 읽은 위치.
int cnt = 0; // 반복 횟수.
while (cnt <= 50000000 && pid < cmdSize) {
    ++cnt;

    pid = doStep(arr, commandCode, pid, inputCode);
}

if (pid == cmdSize) { // 해당 명령어를 모두 읽어들임.
    return TERMINATES();
} else { // 도중에 무한루프가 발생.
    // 일단 50000000번만큼 이동한 위치를 기억해 둔 상태에서
    // 50000000번만큼 다시 명령어를 읽어 들임.
    // 그때, 최대 위치가 닫는 괄호의 위치이고
    // 최소 위치는 여는 괄호의 위치 - 1임.

    int maxPid = pid; // 닫는 괄호의 위치
    int minPid = pid; // 여는 괄호의 위치

    while (cnt-- > 0) {
        pid = doStep(arr, commandCode, pid, inputCode);
        maxPid = Math.max(maxPid, pid);
        minPid = Math.min(minPid, pid);
    }
    return LOOPS(minPid - 1, maxPid);
}

 

 

코드를 보면 알수있다시피, 현재 위치에서 50,000,000 번의 연산을 한 번 더 돌려서 계속 반복하는 최소 idx 와 최대 idx 를 구했다. 어짜피 이미 한 번의 50,000,000 번의 연산이 지나간 이후인데다가, 무한 루프가 확실한 상황이기 때문에, 다시 또 50,000,000 번을 돌리면, 무한 루프에 해당하는 반복문만 계속해서 돌 것이기 때문이다.

 

 

최종 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
    static int pointerPos;
    static int inputPos;
    static int[] shortCut;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());
        StringBuilder answer = new StringBuilder();
        while (T-- > 0) {
            st = new StringTokenizer(br.readLine());
            int arrSize = Integer.parseInt(st.nextToken()); // 배열의 크기
            int cmdSize = Integer.parseInt(st.nextToken()); // 배열의 크기
            int inputSize = Integer.parseInt(st.nextToken()); // input의 길이

            String commandCode = br.readLine();
            String inputCode = br.readLine();

            int [] arr = new int[arrSize];

            answer.append(simulation(arr, commandCode, inputCode)).append("\n");
        }

        bw.write(answer.toString());
        bw.flush();
        bw.close();
        br.close();
    }

    public static String simulation(int[] arr, String commandCode, String inputCode) {
        int cmdSize = commandCode.length();

        pointerPos = 0; // 포인터가 가리키는 위치.
        inputPos = 0; // inputCode의 현재 입력받아야하는 위치.

        shortCut = getShortCut(commandCode);

        int pid = 0; // 특정 명령어를 읽은 위치.
        int cnt = 0; // 반복 횟수.
        while (cnt <= 50000000 && pid < cmdSize) {
            ++cnt;

            pid = doStep(arr, commandCode, pid, inputCode);
        }

        if (pid == cmdSize) { // 해당 명령어를 모두 읽어들임.
            return TERMINATES();
        } else { // 도중에 무한루프가 발생.
            // 일단 50000000번만큼 이동한 위치를 기억해 둔 상태에서
            // 50000000번만큼 다시 명령어를 읽어 들임.
            // 그때, 최대 위치가 닫는 괄호의 위치이고
            // 최소 위치는 여는 괄호의 위치 - 1임.

            int maxPid = pid; // 닫는 괄호의 위치
            int minPid = pid; // 여는 괄호의 위치

            while (cnt-- > 0) {
                pid = doStep(arr, commandCode, pid, inputCode);
                maxPid = Math.max(maxPid, pid);
                minPid = Math.min(minPid, pid);
            }
            return LOOPS(minPid - 1, maxPid);
        }
    }

    public static int doStep(int[] arr, String commandCode, int pid, String inputCode) {
        char c = commandCode.charAt(pid);
        switch (c) {
            case '-':
                arr[pointerPos] = (arr[pointerPos] - 1) < 0 ? 255 : (arr[pointerPos] - 1);
                break;
            case '+':
                arr[pointerPos] = (arr[pointerPos] + 1) > 255 ? 0 : (arr[pointerPos] + 1);
                break;
            case '<':
                pointerPos = (pointerPos - 1) == -1 ? arr.length - 1 : (pointerPos - 1);
                break;
            case '>':
                pointerPos = (pointerPos + 1) == arr.length ? 0 : (pointerPos + 1);
                break;
            case '[':
                if (arr[pointerPos] == 0) {
                    pid = shortCut[pid]; // 현재 위치를 닫는 괄호의 위치로 점프함.
                }
                break;
            case ']':
                if (arr[pointerPos] != 0) {
                    pid = shortCut[pid]; // 현재 위치를 여는 괄호의 위치로 점프함.
                }
                break;
            case '.':
                break;
            case ',':
                arr[pointerPos] = (inputPos == inputCode.length()) ? 255 : inputCode.charAt(inputPos++);
        }
        pid++;

        return pid;
    }

    public static int[] getShortCut(String commandCode) {
        int cmdSize = commandCode.length();
        int[] result = new int[cmdSize]; // 서로 연결되어있는 괄호의 위치.
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < cmdSize; i++) {
            char c = commandCode.charAt(i);

            if (c == '[') {
                stack.push(i);
            } else if (c == ']') { // 닫는 괄호와 여는 괄호를 서로 연결시켜 줌.
                int temp = stack.peek();
                result[i] = temp; // 여는 괄호에는 닫는 괄호의 위치를
                result[temp] = i; // 닫는 괄호에는 여는 괄호의 위치를 저장함.
                stack.pop();
            }
        }

        return result;
    }

    public static String LOOPS(int startIdx, int endIdx) {
        return "Loops " + startIdx + " " + endIdx;
    }

    public static String TERMINATES() {
        return "Terminates";
    }
}

 

 

결론.

뭔가 이상하다 싶을 땐 로직을 (매우 깊게) 생각해보자.

전제 조건이 잘못된 것은 아닌지.. 아니면 사고 회로에 허점은 없는지...

문제의 서술이 불친절하거나 어려운 개념이라면 더더욱 문제를 잘읽고 이해하는 것이 중요하다.

그에 따른 나의 로직을 철저히 정리하는 것이 최우선이 되어야 한다.