[Java] 백준 3954번 : Brainf**k 인터프리터

1. 문제

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

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

 

 

 

2. 풀이과정

문제도 문제지만, 이해가 어려웠던 문제였다..

 

헷갈렸던 부분을 정리해보면,

1) - : -1이 되는 순간 255로! 즉 숫자는 0~255까지만 취급한다.

2) 명령 실행 횟수가 50_000_000초과하면, 현재 상태는 무한 루프를 돌고 있는 것이다. 정상 종료는 그 전에 끝나는 경우다.

 

해결 방법 : 무한 루프 외엔 일반 계산이다. 무한 루프에서, 어디서 루프를 도는지 확인하기 위해 50_000_000번을 추가로 돌려서 무한 루프 도는 구간 중에서 제일 큰 범위의 loop를 찾는다.

 

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

public class Boj3954 {
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		int T = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		
		for(int t=0; t<T; t++) {
			st = new StringTokenizer(br.readLine());
			int N = Integer.parseInt(st.nextToken());//배열(메모리) 크기
			int M = Integer.parseInt(st.nextToken());//명령 = 코드 크기
			int K = Integer.parseInt(st.nextToken());//입력 = 문자열
			int arr[] = new int[N];//배열(메모리)
			int p = 0, inp=0;//arr'spointer & input's pointer
			char[] codes = br.readLine().toCharArray();
			char[] inputs = br.readLine().toCharArray();
			
			//괄호 위치 저장
			int stoe[] = new int[M];
			int etos[] = new int[M];
			Stack<Integer> stack = new Stack<>();
			for(int i=0; i<M; i++) {
				if(codes[i]=='[') {stack.push(i);}
				else if(codes[i]==']') {
					int pos = stack.pop();
					stoe[pos] = i;
					etos[i] = pos;
				}
			}
			
			//명령어 실행
			int cnt = 0;//명령수행횟수
			int result = 0;
			for(int i=0; i<M; i++) {
				
				switch(codes[i]) {
				case '+':
					arr[p] = (arr[p]+1)%256;
					break;
				case '-':
					arr[p] = (arr[p]+255)%256;
					break;
				case '<':
					p = (p-1+N)%N;
					break;
				case '>':
					p = (p+1)%N;
					break;
				case '[':
					if(arr[p]==0) {//루프 안 해도된다.
						//']'찾기
						i = stoe[i];
					}
					break;
				case ']':
					if(arr[p]!=0) {
						if(cnt>50_000_000) {
							result = Math.max(result, i);
						}
						i=etos[i];//시작 위치로!
					}
					break;
				case ',':
					//입력이 더이상 없을 때
					arr[p]=(inp>=K)?255:inputs[inp++];
					break;
				default:
					continue;
				}
				cnt++;
				if(cnt>100_000_000) {
					break;
				}
			}
			//출력
			if(cnt>50_000_000) {
				sb.append("Loops ").append(etos[result]).append(" ").append(result).append("\n");
			}
			else{
				sb.append("Terminates\n");
			}
		}
		System.out.println(sb.toString());
	}
}