[BOJ] 3954 Brainf**k 인터프리터 - JAVA

1. 문제

3954번: Brainf**k 인터프리터

Brainf**k 프로그램이 주어졌을 때, 이 프로그램이 끝나는지, 무한 루프에 빠지는지 알아내는 프로그램을 작성하시오.

무한 루프란, 특정 시점부터 탈출하지 않고 무한히 반복 실행되는 루프를 말한다.

Brainf**k 인터프리터는 정수를 담는 하나의 배열(unsigned 8-bit 정수)과, 그 배열의 칸 하나를 가리키는 포인터로 이루어져 있다. Brainf**k 프로그램은 다음과 같이 8개의 명령어로 이루어져 있다.

-	포인터가 가리키는 수를 1 감소시킨다. (modulo 2^8=256)
+	포인터가 가리키는 수를 1 증가시킨다. (modulo 2^8=256)
<	포인터를 왼쪽으로 한 칸 움직인다.
>	포인터를 오른쪽으로 한 칸 움직인다.
[	만약 포인터가 가리키는 수가 0이라면, [ 와 짝을 이루는 ] 의 다음 명령으로 점프한다.
]	만약 포인터가 가리키는 수가 0이 아니라면, ] 와 짝을 이루는 [ 의 다음 명령으로 점프한다.
.	포인터가 가리키는 수를 출력한다.
,	문자 하나를 읽고 포인터가 가리키는 곳에 저장한다. 입력의 마지막(EOF)인 경우에는 255를 저장한다.

인터프리터는 Brainf**k 프로그램의 첫 번째 명령부터 수행하고, 더이상 수행할 명령이 없다면, 프로그램을 종료한다. 각 명령을 수행하고 나면, 다음 명령을 수행한다. 물론 [이나 ]인 경우에는 다음 명령으로 이동하는 것이 아니라 점프를 한다.

데이터 배열의 크기는 문제에서 주어지는 값을 사용해야 한다. 또, 데이터 배열의 값이 underflow나 overflow를 일으켰을 때는 일반적인 방법을 따르면 된다. 프로그램을 수행하기 전에, 데이터 배열의 값은 0으로 초기화되어 있고, 포인터가 가리키는 칸은 0번 칸이다.

포인터를 왼쪽이나 오른쪽으로 움직일 때, 데이터 배열의 범위를 넘어간다면, 반대쪽으로 넘어가게 된다. 즉, 포인터가 0을 가리킬 때, 1을 감소시킨다면, 배열의 크기 - 1번째를 가리키게 된다.

[와 ]는 루프를 의미하며, 중첩될 수 있다. 입력으로 주어진 프로그램은 잘 짜여 있음이 보장된다. 즉 프로그램을 왼쪽에서 오른쪽으로 훑으면서 [의 개수에서 ]의 개수를 빼면 항상 0보다 크거나 같고, 맨 끝까지 훑으면 그 값은 0이 된다.

이 문제는 Brainf**k 프로그램이 무한 루프에 빠지는지 안 빠지는지를 검사하기만 하면 된다. 따라서, 출력은 무시한다.

 

각 테스트 케이스에 대해서, 프로그램이 종료된다면 "Terminates"를, 무한 루프에 빠지게 된다면 "Loops"를 출력한다. 무한 루프에 빠졌을 때는, 프로그램의 어느 부분이 무한 루프인지를 출력한다. ([와 ]의 위치) 프로그램이 명령어를 50,000,000번 이상 수행한 경우, 프로그램은 항상 종료되었거나 무한 루프에 빠져있다. 무한 루프일 경우, 해당 루프는 적어도 한 번 실행이 완료된 상태이며, 한 번의 무한 루프에서 실행되는 명령어의 개수는 50,000,000개 이하이다.

---

2. 풀이

고려해야할 테스트케이스

출처 : https://www.acmicpc.net/board/search/all/problem/3954

이 코드가 다 맞다면 정답이라고 보면 된다.

3 209 1 +[>+[>----------------------------------[+++]<+]++++++++++++++++++++++++++[+]<+],[-].+[-[[>+[>----------------------------------[+++]<+]++++++++++++++++++++++++++[+]<+]----------------------------------[+]]++] 1	Loops 86 208 5천만번째에서 ] 명령이 실행되는 경우
65359 16 3 +[>+],...[[-],+] 999	Terminates 5천만번에서 명령이 끝나는 경우
65359 16 3 +[>+],[[-],+]+[] 999	Loops 14 15
3 124 1 +[-[[>+[>----------------------------------[+++]<+]++++++++++++++++++++++++++[+]<+]----------------------------------[+]]++] .	Loops 1 123 가장 바깥쪽 루프가 무한루프일 때
1 8 1 +[-[]++] .	Loops 3 4 안쪽 루프가 무한루프일 때
10 5 1 +[[]] a	Loops 2 3 안쪽 루프가 무한루프일 때
1 9 1 ++[[++]+] a	Loops 3 6 안쪽 루프가 무한루프일 때
10 9 3 +[-[><]-] qwe	Loops 3 6 안쪽 루프가 무한루프일 때

 

테스트케이스 밖에서 사용한 변수들

stack은 어차피 항상 비워지기때문에(문제 조건) 밖에 선언했다.

BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int T = Integer.parseInt(in.readLine());
StringBuilder sb = new StringBuilder();
int END = 50000000;
int mod = 256;
Stack<Integer> stack = new Stack<>();

 

테스트케이스 속 변수들

st = new StringTokenizer(in.readLine());
int M = Integer.parseInt(st.nextToken());//메모리(배열)크기
int C = Integer.parseInt(st.nextToken());//프로그램 코드 크기
int I = Integer.parseInt(st.nextToken());//입력 크기

int[] arr = new int[M];//메모리

String command = in.readLine();//프로그램 코드
String input = in.readLine();//입력

 

[, ] 짝 맞추는 부분

stack을 활용해서 서로의 인덱스를 pair배열에 넣었다. 방식이 [BOJ] 9012 괄호와 비슷해서 쉽게 풀었다.

int[] pair = new int[C];
for (int c = 0; c < C; c++) {
   if (command.charAt(c) == '[') {
      stack.push(c);
   } else if (command.charAt(c) == ']') {
      pair[c] = stack.peek();
      pair[stack.pop()] = c;
   }
}

 

명령 수행 부분

pointer	메모리 가리키는 포인터 위치
ipos	다음 입력 위치
count	명령 수행 횟수
min, max	명령 수행 횟수가 5천만번을 넘어갔을 때 반복하는 구간의 최소, 최대값

1.  명령문 크기만큼 for문을 돌린다. 명령 접근을 위한 c 변수, 명령 횟수를 세기 위한 count 변수를 둘 다 가지고 있어야 한다.

2.  만약 명령 수행 횟수(count)가 5천만번이라면, min과 max 값을 현재의 c값으로 바꾼다. 5천만번 이상 1억번 이하까지 전부 비교하면서 그때의 c값과 저장된 min,max값을 비교할 것이다. 5천만번 이상 1억번 이하에서 한 명령이 확실하게 끝난다고 되어 있으므로 포인터가 움직이는 최소값과 최대값이 바로 괄호의 범위가 된다.

3.  만약 count가 1억번 이상이 되었다면 끝낸다. 최소값이 [의 바로 다음 인덱스위치로 저장돼있기때문에 min-1을 출력해야한다.

4.  반복문이 끝났을 때, count가 END보다 같거나 작다면 정상적으로 끝난것이므로 Terminates를 출력한다.

5.  명령수행은 switch-case로 했다.

    5-1.  -는 포인터가 가리키는 메모리값을 -1한다. 최대값이 255이므로 %을 활용한다.  

    5-2.  +는 포인터가 가리키는 메모리값을 +1한다. 마찬가지로 %을 활용한다.

    5-3.  <는 포인터를 -1한다. 인덱스오류를 피하기 위해 pointer+M-1값에 %M을 한다.

    5-4.  >는 포인터를 +1한다. 이 명령도 %M해야한다.

    5-5.  [이고 포인터가 가리키는 값이 0일때 다음 짝괄호로 가야한다. pair배열에 저장된 값으로 c를 변경한다.

    5-6.  ]이고 포인터가 가리키는 값이 0이 아닐 때 이전 짝괄호로 가야한다. pair배열에 저장된 값으로 c를 변경한다.

    5-7.  .이면 출력이므로 무시한다.

    5-8.  ,이면 ipos위치를 포인터가 가리키는 곳에 저장한 뒤에 +1한다. 만약 ipos가 I와 같다면 255를 저장한다.

int pointer = 0;
int ipos = 0;
int count = 0;
int min=0,max=0;
for (int c = 0; c < C; c++) {
   int now = command.charAt(c);
   if(++count==END){
      min = max = c;
   }

   if(count>END){
      min = Math.min(min,c);
      max = Math.max(max,c);
   }

   if(count>END*2){
      sb.append("Loops ").append(min-1).append(' ').append(max).append('\n');
      break;
   }

   switch (now) {
      case '-'://underflow
         arr[pointer] = (arr[pointer] +255) % mod;
         break;
      case '+'://overflow
         arr[pointer] = (arr[pointer] + 1) % mod;
         break;
      case '<':
         pointer = (pointer + M - 1) % M;
         break;
      case '>':
         pointer = (pointer + 1) % M;
         break;
      case '[':
         if(arr[pointer]==0){
            c = pair[c];
         }
         break;
      case ']':
         if(arr[pointer]!=0){
            c = pair[c];
         }
         break;
      case '.': break;
      case ',':
         arr[pointer] = ipos < I ? input.charAt(ipos++) : 255;
         break;
   }

}

if (count<=END) {
   sb.append("Terminates\n");
}

---

3. 결과

세번 다 18%에서 틀렸다. 가장 안쪽의 []만 챙기고 바깥의 []에서 반복했을 경우를 놓친 걸 몰랐다.

처음으로 맞았을 때는 pair로 배열이 아니라 Map을 사용했다. 다른 사람들보다 메모리가 너무 많이 들어서 Map을 배열로 변경했다.

배열로 변경한 결과 메모리와 시간이 엄청나게 많이 줄어들었다.

마지막으로 제출한 건 stack 객체 생성을 테스트케이스 들어가기 전 바깥에 한 코드다. 시간이 워낙 오래걸리는 코드라 바꿨을 때 500ms가 더 걸렸지만 그건 별 의미 없는 것 같고 메모리는 살짝 줄었다.