[백준 온라인 저지(BOJ)] 3954번 Brainfuck 자바(java) 풀이

백준 온라인 저지(BOJ) 3954번 Brainfuck 문제

안녕하세요 호호만두에요

이번에는 백준 온라인 저지(BOJ)의 3954번 문제인 Brainfuck을 풀어봤어요

이름이 너무 웃기지 않나요?? 들어가보면 사실 Brainf**k로 표현되어있어요

찾아보니까 이런 단어가 존재하더라구요??? 그게 더 신기...

알고보니까 93년도에 우어반 뮐러라는 사람이 만든 프로그래밍 언어라고 ㅋㅋㅋㅋㅋㅋ

이름 한 번 잘지었네 위키에서 명령어들 같은거 보면 그대로 규칙이 그대로 나왔어요

궁금하신 분은 쭉 훑어보세요
brainfuck 이란??

이 문제는 골드1로 분류되어 있는 난이도가 조금 있는 문제였어요

BOJ 3954번 Brainfuck

이 문제의 유형을 분류하자면 주어진 사항을 잘 읽고 구현하는 시뮬레이션

그리고 규칙 찾기 문제로 분류 할 수 있을 것 같아요

그러면 풀어 봅시다!!

---

문제의 핵심

이 문제는 문제를 이해하는게 제일 중요하다고 생각합니다.
메모리 배열의 위치를 참조하는 pointer 개념과
읽은 input의 위치를 참조하는 index를 활용하고
짝이 되는 bracket의 위치를 잘 찾는다면 풀 수 있습니다.

---

문제 풀이

이 문제는 주어진 사항을 그대로 구현하는 문제에요

1. 먼저 '['와 ']' 쌍을 for문을 돌면서 모두 찾습니다. 찾아서 쌍의 index를 배열에 저장합니다.
2. 그 다음 program 명령에 맞게 switch문을 이용해 판단하여 수행합니다

• 2-1. '-'와 '+'는 포인터가 가리키고 있는 메모리의 값을 1 감소, 증가 시켜줍니다(% 256)
  • 2-2. '<' '>'는 포인터의 위치를 감소, 증가 시킵니다. 인덱스를 넘어가는 경우 예외처리를 해줍니다
    • 2-3. '['와 ']'는 메모리 배열의 숫자를 참조하여 jump를 하거나 순차적으로 program 명령을 진행합니다.
      • 2.4 '.'은 그냥 넘어가고 ','는 input string의 한 문자를 읽어서 아스키 코드 값 메모리 배열에 저장합니다. (input을 다 읽은 경우 255 저장)

3. loop문이 몇번 도는지 검사하며 50000000이 넘으면 무한루프에 빠졌다고 인식하여 Loops 출력
4. 그렇지 않고 모든 program code를 다 읽은 경우에는 Terminates를 출력합니다

백준 3954번 자바 풀이 코드

• github주소 아래 링크
  백준3954번 Brainfuck

  import java.io.BufferedReader;
  import java.io.BufferedWriter;
  import java.io.IOException;
  import java.io.InputStreamReader;
  import java.util.Arrays;
  import java.io.OutputStreamWriter;
  import java.util.Stack;
  

class Pair{
int left;
int right;

Pair(int left, int right){
    this.left = left;
    this.right = right;
}

}

class Main {
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static int mem_size;
static int code_len;
static int input_size;

static int inputIdx;
static int memIdx;
static int[] mem;

static String text;
static String program;

static int loopCount;

static Stack<Integer> stack;
static Pair [] pairs;

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

    init();

    int testNum = Integer.parseInt(br.readLine());

    // test 개수
    for(int i=0; i<testNum; i++){
        String[] temp = br.readLine().split(" ");
        mem_size = Integer.parseInt(temp[0]);
        code_len = Integer.parseInt(temp[1]);
        input_size = Integer.parseInt(temp[2]);

        program = br.readLine();
        text = br.readLine();

        // '[', ']' 검사
        readBracket();

        solve();

        bw.newLine();

        init();
    }
    bw.flush();

    br.close();
    bw.close();
}

public static void readBracket(){
    for(int i=0; i<code_len; i++){
        if(program.charAt(i) == '['){
            stack.push(i);
            pairs[i] = new Pair(i, 0);
        }
        else if(program.charAt(i) == ']'){
            int temp = stack.pop();
            pairs[i] = new Pair(temp, i);
            pairs[temp].right = i;
        }
    }
}

public static void solve() throws IOException{
    // Read program
    int idx = 0;
    int max_index = 0;

    while(true){
        char command = program.charAt(idx);

        switch(command){
            case '-':
                mem[memIdx] = ( mem[memIdx] - 1 ) % 256;
                break;
            case '+':
                mem[memIdx] = ( mem[memIdx] + 1 ) % 256;
                break;
            case '<':
                if(memIdx == 0)
                    memIdx = mem_size - 1;
                else
                    memIdx--;
                break;
            case '>':
                if(mem_size-1 == memIdx)
                    memIdx = 0;
                else
                    memIdx++;
                break;
            case '[':
                if(mem[memIdx] == 0){
                    idx = pairs[idx--].right;
                    loopCount++;
                }
                break;
            case ']':
                if(mem[memIdx] != 0){
                    idx = pairs[idx--].left;
                    loopCount++;
                }
                break;
            case '.':
                break;
            case ',':
                if(inputIdx == input_size)
                    mem[memIdx] = 255;
                else
                    mem[memIdx] = (int)text.charAt(inputIdx++);
        }

        idx++;
        loopCount++;
        // loop문 도는 경우 갇힌 loop문 판단을 위한 index
        if(idx > max_index)
            max_index = idx;

        // 모든 명령 다 읽음
        if(idx == code_len){
            bw.write("Terminates");
            break;
        }
        if(loopCount > 50000000){
            bw.write("Loops" + " " + pairs[max_index].left + " " + pairs[max_index].right);
            break;
        }
    }
}

public static void init(){
    inputIdx = 0;
    memIdx = 0;
    loopCount = 0;

    stack = new Stack<>();
    pairs = new Pair[4096];

    mem = new int[100001];
    Arrays.fill(mem, 0);
}

}