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

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

 

 

 

본 게시글은 다음 포스팅의 후속편입니다. (그때 해결 못해서 ...)

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

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

 

계산을 좀더 간편하게 하는 방법.

= 미리 각 [ 명령어와 ] 명령어 마다, 점프할 위치를 저장해 놓는다.

 

저장해 놓는 방법.

stack 을 이용해서 [ 명령어가 나올때마다 순서대로 쌓아놓는다.

★이때 [ 명령어의 index 번호도 함께!

 

그렇게되면, 추후에 ] 명령어가 나올때, stack 의 가장 윗 순서의 요소를 pop() 하면 가장 최근의 [ 명령어의 index를 얻을 수 있다. -->> 이를 이용해서, [ 명령어의 index 와 ] 명령어의 index (현재 index) 를 연결할 수 있게 된다!

 

그걸 구현한게 바로 다음 코드다.

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

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

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

    return shortCuts;
}

 

 

---

그래서 도달한 전체 코드는 다음과 같다.

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

public class Main {
//    static int LOOP_LIMITS = 10;
    static int LOOP_LIMITS = 50000000;
    static int IDX = 0;
    static byte[] ARRAY = null;
    static int[] SHORT_CUTS = null;
    static ArrayDeque<Character> INPUTS = null;
    static int POINTER = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        for (int i=0; i<n; i++) {
            int[] sizes = getIntArr(br.readLine().split(" "));

            ARRAY = new byte[sizes[0]];
            char[] commands = br.readLine().toCharArray(); // length 는 sizes[1]
            INPUTS = getCharQue(br.readLine().toCharArray()); // length 는 sizes[2]

            SHORT_CUTS = getShortCuts(commands); // COMMANDS 배열의 length = sizes[1]

            System.out.println(simulation(commands));
        }
    }

    static void initLoopsLimit() {
//        LOOP_LIMITS = 10;
        LOOP_LIMITS = 50000000;
    }

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

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

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

        return shortCuts;
    }

    static String simulation(char[] commands) {

        while (IDX < commands.length) {
            String result = doInterpret(commands[IDX]);
            IDX ++;

            /*
                result 가 null 이면 문제 없이 계속 진행,
                null 이 아니라면 Loops startIdx endIdx 값이 들어있을 것임. ex LOOPS(1, 4)
             */
            if (result != null) return result;
        }

        return TERMINATES(); // 여기까지 왔다는 것은 모든 명령을 문제 없이 끝냈다는 것.
    }

    static String doInterpret(char command) {
        byte value = ARRAY[POINTER]; // 현재 배열 값
//        System.out.println("현재 배열 값 : " + value);

//        System.out.println("[POINTER]" + pointer + " ARRAY[POINTER]" + value
//                + " [command]" + command + " [input]" + INPUTS.peekFirst());

        switch (command) {
            case '-': // 값 감소
                ARRAY[POINTER] = (value == 0) ? 127 : (byte) (value - 1);
                break;
            case '+': // 값 증가
                ARRAY[POINTER] = (value == 127) ? 0 : (byte) (value + 1);
                break;
            case '<': // 자리 감소
                decreasePointer();
                break;
            case '>': // 자리 증가
                increasePointer();
                break;
            case '[': // 반복문 시작
                if (value == 0) { // 0 이면 해당 반복문 JUMP();
//                    System.out.println("jump 이전 IDX : " + IDX);
                    IDX = SHORT_CUTS[IDX];
//                    System.out.println("jump 이후 IDX : " + IDX);
                }
                else {
                    LOOP_LIMITS --;
                }
                break;
            case ']': // 반복문 끝
                if (value == 0) { // 0 이면 그냥 지나간다.
                    initLoopsLimit();
                }
                else { // 짝궁 [ 명령어 위치까지 되돌아간다.
//                    System.out.println("jumpBack 이전 IDX : " + IDX);
                    int endIdx = IDX;
                    IDX = SHORT_CUTS[IDX];
//                    System.out.println("jumpBack 이후 IDX : " + IDX);
                    int startIdx = IDX;

                    if (LOOP_LIMITS == 0) {
                        return LOOPS(startIdx, endIdx);
                    }

                    IDX --;
                }
                break;
            case ',': // 문자 -> ASCII 변환
                if (INPUTS.isEmpty()) ARRAY[POINTER] = (byte) 255; // 입력의 마지막(EOF)인 경우에는 255를 저장
                else {
                    char ch = INPUTS.poll();
                    ARRAY[POINTER] = (byte) ch;
                }
                break;
            default: // (아마도) `.`
                break;
        }

//        System.out.println(" --> [POINTER]" + POINTER + " ARRAY[POINTER]" + ARRAY[POINTER]);
        return null;
    }

    static void decreasePointer() {
        int pointer = POINTER;
        POINTER = (pointer == 0) ? ARRAY.length - 1 : pointer - 1;
    }

    static void increasePointer() {
        int pointer = POINTER;
        POINTER = (pointer == ARRAY.length - 1) ? 0 : pointer + 1;
    }

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

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

    static ArrayDeque<Character> getCharQue(char[] chrArr) {
        ArrayDeque<Character> result = new ArrayDeque<>();
        for (char chr : chrArr) {
            result.add(chr);
        }
        return result;
    }

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

 

 

하.. 하지만.. 4% 까지 오르더니...

 

 

무언가 큰 잘못이 발생한 것이 틀림없다.

 

문제점. 문제를 잘 이해해보자 ....

문제에 보면 다음과 같이 쓰여있다.

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

 

.. 나는 하나의 반복문이 50,000,000 번 이상 수행해야 하는 건지 알았다.

근데 전체 명령어로 따지는 거더라고?

 

그래서 전체 코드를 바꿔보았다.

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

public class Main {
//    static final int LOOP_LIMITS = 10;
    static final int LOOP_LIMITS = 50000000;
    static int IDX = 0;
    static byte[] ARRAY = null;
    static int[] SHORT_CUTS = null;
    static ArrayDeque<Character> INPUTS = null;
    static int POINTER = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        for (int i=0; i<n; i++) {
            int[] sizes = getIntArr(br.readLine().split(" "));

            ARRAY = new byte[sizes[0]];
            char[] commands = br.readLine().toCharArray(); // length 는 sizes[1]
            INPUTS = getCharQue(br.readLine().toCharArray()); // length 는 sizes[2]

            SHORT_CUTS = getShortCuts(commands); // COMMANDS 배열의 length = sizes[1]

            System.out.println(simulation(commands));
        }
    }

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

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

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

        return shortCuts;
    }

    static String simulation(char[] commands) {

        int executionCount = 0;

        while (IDX < commands.length) {

            char command = commands[IDX];
            doInterpret(command);

            executionCount ++;
            if (executionCount > LOOP_LIMITS) {
                int startIdx = IDX;
//                System.out.println("초과 발생!! [executionCount]" + executionCount);
//                System.out.print(startIdx + "-->");
                while (commands[startIdx] != '[')
                    startIdx --;
//                System.out.println(startIdx);
                int endIdx = SHORT_CUTS[startIdx];

                return LOOPS(startIdx, endIdx);
            }

            IDX ++;
        }

        return TERMINATES(); // 여기까지 왔다는 것은 모든 명령을 문제 없이 끝냈다는 것.
    }

    static void doInterpret(char command) {
        byte value = ARRAY[POINTER]; // 현재 배열 값

        switch (command) {
            case '-': // 값 감소
                ARRAY[POINTER] = (value == 0) ? 127 : (byte) (value - 1);
                break;
            case '+': // 값 증가
                ARRAY[POINTER] = (value == 127) ? 0 : (byte) (value + 1);
                break;
            case '<': // 자리 감소
                decreasePointer();
                break;
            case '>': // 자리 증가
                increasePointer();
                break;
            case '[': // 반복문 시작
                if (value == 0) { // 0 이면 해당 반복문 JUMP();
//                    System.out.println("jump 이전 IDX : " + IDX);
                    IDX = SHORT_CUTS[IDX];
//                    System.out.println("jump 이후 IDX : " + IDX);
                }
                break;
            case ']': // 반복문 끝
                if (value == 0) {
                    // 0 이면 그냥 지나간다.
                }
                else { // 짝궁 [ 명령어 위치까지 되돌아간다.
//                    System.out.println("jumpBack 이전 IDX : " + IDX);
                    IDX = SHORT_CUTS[IDX];
//                    System.out.println("jumpBack 이후 IDX : " + IDX);

//                    IDX --;
                }
                break;
            case ',': // 문자 -> ASCII 변환
                if (INPUTS.isEmpty()) ARRAY[POINTER] = (byte) 255; // 입력의 마지막(EOF)인 경우에는 255를 저장
                else {
                    char ch = INPUTS.poll();
                    ARRAY[POINTER] = (byte) ch;
                }
                break;
            default: // (아마도) `.`
                break;
        }

//        System.out.println("[command]" + command + ", 현재 [POINTER]의 (배열)값 : [" + POINTER + "]번째 값은 " + ARRAY[POINTER]);
//        System.out.println(" --> [POINTER]" + POINTER + " ARRAY[POINTER]" + ARRAY[POINTER]);
    }

    static void decreasePointer() {
        int pointer = POINTER;
        POINTER = (pointer == 0) ? ARRAY.length - 1 : pointer - 1;
    }

    static void increasePointer() {
        int pointer = POINTER;
        POINTER = (pointer == ARRAY.length - 1) ? 0 : pointer + 1;
    }

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

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

    static ArrayDeque<Character> getCharQue(char[] chrArr) {
        ArrayDeque<Character> result = new ArrayDeque<>();
        for (char chr : chrArr) {
            result.add(chr);
        }
        return result;
    }

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

 

그런데..

어째서! 왜! 여전히! 

오류가 뜨는 것인가 ............ 모든 테스트 케이스가 맞는데

 

 

문제점. IDX 초기화를 안했다.

여러 테스트 케이스를 시행하니까, static 으로 선언했던 IDX 가 예전 값 그대로에 있었다.

이 문제점을 고치고 나니...

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

public class Main {
//    static final int LOOP_LIMITS = 10;
    static final int LOOP_LIMITS = 50000000;
    static int IDX = 0;
    static byte[] ARRAY = null;
    static int[] SHORT_CUTS = null;
    static ArrayDeque<Character> INPUTS = null;
    static int POINTER = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        for (int i=0; i<n; i++) {
            int[] sizes = getIntArr(br.readLine().split(" "));

            ARRAY = new byte[sizes[0]];
            char[] commands = br.readLine().toCharArray(); // length 는 sizes[1]
            INPUTS = getCharQue(br.readLine().toCharArray()); // length 는 sizes[2]

//            System.out.print("[ARRAY]");
//            printArr(ARRAY);
//
//            System.out.print("[commands]");
//            printArr(commands);
//
//            System.out.print("[INPUTS]");
//            INPUTS.forEach(obj -> System.out.print(obj + " "));
//            System.out.println();

            SHORT_CUTS = getShortCuts(commands); // COMMANDS 배열의 length = sizes[1]

            System.out.println(simulation(commands));
        }
    }

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

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

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

        return shortCuts;
    }

    static String simulation(char[] commands) {

        int executionCount = 0;

        IDX = 0;
        while (IDX < commands.length) {

            char command = commands[IDX];
            doInterpret(command);

            executionCount ++;
            if (executionCount > LOOP_LIMITS) {
                int startIdx = IDX;
//                System.out.println("초과 발생!! [executionCount]" + executionCount);
//                System.out.print(startIdx + "-->");
                while (commands[startIdx] != '[')
                    startIdx --;
//                System.out.println(startIdx);
                int endIdx = SHORT_CUTS[startIdx];

                return LOOPS(startIdx, endIdx);
            }

            IDX ++;
        }

        return TERMINATES(); // 여기까지 왔다는 것은 모든 명령을 문제 없이 끝냈다는 것.
    }

    static void doInterpret(char command) {
        byte value = ARRAY[POINTER]; // 현재 배열 값

        switch (command) {
            case '-': // 값 감소
                ARRAY[POINTER] = (value == 0) ? 127 : (byte) (value - 1);
                break;
            case '+': // 값 증가
                ARRAY[POINTER] = (value == 127) ? 0 : (byte) (value + 1);
                break;
            case '<': // 자리 감소
                decreasePointer();
                break;
            case '>': // 자리 증가
                increasePointer();
                break;
            case '[': // 반복문 시작
                if (value == 0) { // 0 이면 해당 반복문 JUMP();
//                    System.out.println("jump 이전 IDX : " + IDX);
                    IDX = SHORT_CUTS[IDX];
//                    System.out.println("jump 이후 IDX : " + IDX);
                }
                break;
            case ']': // 반복문 끝
                if (value == 0) {
                    // 0 이면 그냥 지나간다.
                }
                else { // 짝궁 [ 명령어 위치까지 되돌아간다.
//                    System.out.println("jumpBack 이전 IDX : " + IDX);
                    IDX = SHORT_CUTS[IDX];
//                    System.out.println("jumpBack 이후 IDX : " + IDX);

//                    IDX --;
                }
                break;
            case ',': // 문자 -> ASCII 변환
                if (INPUTS.isEmpty()) ARRAY[POINTER] = (byte) 255; // 입력의 마지막(EOF)인 경우에는 255를 저장
                else {
                    char ch = INPUTS.poll();
                    ARRAY[POINTER] = (byte) ch;
                }
                break;
            default: // (아마도) `.`
                break;
        }

//        System.out.println("[command]" + command + ", 현재 [POINTER]의 (배열)값 : [" + POINTER + "]번째 값은 " + ARRAY[POINTER]);
//        System.out.println(" --> [POINTER]" + POINTER + " ARRAY[POINTER]" + ARRAY[POINTER]);
    }

    static void decreasePointer() {
        int pointer = POINTER;
        POINTER = (pointer == 0) ? ARRAY.length - 1 : pointer - 1;
    }

    static void increasePointer() {
        int pointer = POINTER;
        POINTER = (pointer == ARRAY.length - 1) ? 0 : pointer + 1;
    }

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

    static ArrayDeque<Character> getCharQue(char[] chrArr) {
        ArrayDeque<Character> result = new ArrayDeque<>();
        for (char chr : chrArr) {
            result.add(chr);
        }
        return result;
    }

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

    static void printArr(byte[] arr) {
        for (byte obj : arr) {
            System.out.print(obj + " ");
        }
        System.out.println();
    }

    static void printArr(char[] arr) {
        for (char obj : arr) {
            System.out.print(obj + " ");
        }
        System.out.println();
    }
}

 

정답률이 9% 까지 올라가다가 다시 틀렸습니다가 떴다.. 왜이럴까 도대체 !!

 

 

혹시 몰라서 static 으로 선언했던 변수를 지역 변수로 바꾸어 보았는데도 ..

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

public class Main {
    //    static final int LOOP_LIMITS = 10;
    static final int LOOP_LIMITS = 50000000;
    static int IDX = 0;
    //    static byte[] ARRAY = null;
//    static int[] SHORT_CUTS = null;
//    static ArrayDeque<Character> INPUTS = null;
    static int POINTER = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        for (int i=0; i<n; i++) {
            int[] sizes = getIntArr(br.readLine().split(" "));

//            ARRAY = new byte[sizes[0]];
            byte[] array = new byte[sizes[0]];

            char[] commands = br.readLine().toCharArray(); // length 는 sizes[1]

//            INPUTS = getCharQue(br.readLine().toCharArray()); // length 는 sizes[2]
            ArrayDeque<Character> inputs = getCharQue(br.readLine().toCharArray()); // length 는 sizes[2]

//            System.out.print("[ARRAY]");
//            printArr(ARRAY);
//
//            System.out.print("[commands]");
//            printArr(commands);
//
//            System.out.print("[INPUTS]");
//            INPUTS.forEach(obj -> System.out.print(obj + " "));
//            System.out.println();

//            SHORT_CUTS = getShortCuts(commands); // COMMANDS 배열의 length = sizes[1]
            int[] shortCuts = getShortCuts(commands); // COMMANDS 배열의 length = sizes[1]

            System.out.println(simulation(array, commands, inputs, shortCuts));
        }
    }

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

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

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

        return shortCuts;
    }

    static String simulation(byte[] array, char[] commands, ArrayDeque<Character> inputs, int[] shortCuts) {

        int executionCount = 0;

        IDX = 0;
        POINTER = 0;
        while (IDX < commands.length) {

            char command = commands[IDX];
            doInterpret(array, command, inputs, shortCuts);

            executionCount ++;
            if (executionCount > LOOP_LIMITS) {
                int startIdx = IDX;
//                System.out.println("초과 발생!! [executionCount]" + executionCount);
//                System.out.print(startIdx + "-->");
                while (commands[startIdx] != '[')
                    startIdx --;
//                System.out.println(startIdx);

//                int endIdx = SHORT_CUTS[startIdx];
                int endIdx = shortCuts[startIdx];

                return LOOPS(startIdx, endIdx);
            }

            IDX ++;
        }

        return TERMINATES(); // 여기까지 왔다는 것은 모든 명령을 문제 없이 끝냈다는 것.
    }

    static void doInterpret(byte[] array, char command, ArrayDeque<Character> inputs, int[] shortCuts) {
        byte value = array[POINTER]; // 현재 배열 값

        switch (command) {
            case '-': // 값 감소
                array[POINTER] = (value == 0) ? 127 : (byte) (value - 1);
                break;
            case '+': // 값 증가
                array[POINTER] = (value == 127) ? 0 : (byte) (value + 1);
                break;
            case '<': // 자리 감소
                decreasePointer(array.length);
                break;
            case '>': // 자리 증가
                increasePointer(array.length);
                break;
            case '[': // 반복문 시작
                if (value == 0) { // 0 이면 해당 반복문 JUMP();
//                    System.out.println("jump 이전 IDX : " + IDX);
                    IDX = shortCuts[IDX];
//                    System.out.println("jump 이후 IDX : " + IDX);
                }
                break;
            case ']': // 반복문 끝
                if (value == 0) {
                    // 0 이면 그냥 지나간다.
                }
                else { // 짝궁 [ 명령어 위치까지 되돌아간다.
//                    System.out.println("jumpBack 이전 IDX : " + IDX);
                    IDX = shortCuts[IDX];
//                    System.out.println("jumpBack 이후 IDX : " + IDX);

//                    IDX --;
                }
                break;
            case ',': // 문자 -> ASCII 변환
                if (inputs.isEmpty()) array[POINTER] = (byte) 255; // 입력의 마지막(EOF)인 경우에는 255를 저장
                else {
                    char ch = inputs.poll();
                    array[POINTER] = (byte) ch;
                }
                break;
            default: // (아마도) `.`
                break;
        }

//        System.out.println("[command]" + command + ", 현재 [POINTER]의 (배열)값 : [" + POINTER + "]번째 값은 " + ARRAY[POINTER]);
//        System.out.println(" --> [POINTER]" + POINTER + " ARRAY[POINTER]" + ARRAY[POINTER]);
    }

    static void decreasePointer(int arrayLength) {
        int pointer = POINTER;
        POINTER = (pointer == 0) ? arrayLength - 1 : pointer - 1;
    }

    static void increasePointer(int arrayLength) {
        int pointer = POINTER;
        POINTER = (pointer == arrayLength - 1) ? 0 : pointer + 1;
    }

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

    static ArrayDeque<Character> getCharQue(char[] chrArr) {
        ArrayDeque<Character> result = new ArrayDeque<>();
        for (char chr : chrArr) {
            result.add(chr);
        }
        return result;
    }

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

    static void printArr(byte[] arr) {
        for (byte obj : arr) {
            System.out.print(obj + " ");
        }
        System.out.println();
    }

    static void printArr(char[] arr) {
        for (char obj : arr) {
            System.out.print(obj + " ");
        }
        System.out.println();
    }
}

 

이번엔 13% 까지 올라갔다가 틀렸습니다가 뜬다 ..

 

 

하 ~ (후_후속편에 계속 .. )

 

 

후_후속편 바로가기

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

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