백준 3954 brainf**k 인터프리터

문제

---

3954번: brainf**k 인터프리터 (acmicpc.net)

해결방법

---

• 인터프리터 구현
  • 각 명령어에 맞게 포인터와 메모리 배열을 변경하기만 하면된다. 괄호는 미리 모든 괄호를 찾아서 짝을 지어준다.
• 무한 루프 찾기
  • 처음엔 문제가 무슨 말인가 했지만 어쨋든 5천만번 수행 시 돌고 있고 돌고 있는 곳이 무한 루프 안이라고 생각하고 문제를 풀었다.
• 무한 루프 구간 찾기
  • 마지막 위치가 구간 안이지만 어떤 괄호가 무한 루프를 도는 괄호인지 찾아야한다. 그걸 위해 5천만번을 더 수행하면서 그 때 포인터가 도달하는 가장 큰 값의 괄호와 가장 작은 값의 괄호가 무한 루프가 된다.

동작과정

---

1. 명령어의 괄호를 모두 찾아서 서로의 짝을 가르키게 한다.
2. 반복문을 5천만번 혹은 명령어의 끝까지 수행한다.
3. 명령어에 끝에 도달했다면 무한루프에 빠지지 않았으므로 Terminates 출력한다.
4. i가 아직 명령어의 내부에 있다면 무한루프에 빠진 것이므로 무한루프에 해당하는 [, ] 를 찾아야한다.
5. 다시 한번 5천만번의 명령어를 수행하며 i 가 도달하는 곳의 제일 오른쪽과 제일 왼쪽을 저장한다.
6. 제일 왼쪽과 제일 오른쪽이 무한 루프를 일으키는 괄호 이므로 Loop min max 를 출력한다.
   • 이 때 min을 비교할 때 i는 왼쪽 괄호에 갓다가 i++을 통해 1증가된 값이기 때문에 min 대신 min-1 을 출력한다.

코드

---

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

public class Main {
	
	private static int pointer, input, M, C, I;
	private static int[] memory, loops;
	private static String commands, inputs;

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();

		// T 만큼 반복 수행
		int T = Integer.parseInt(in.readLine());
		for (int t = 0; t < T; t++) {
			StringTokenizer st = new StringTokenizer(in.readLine());

			// 메모리 크기, 명령어 길이, 입력 길이
			M = Integer.parseInt(st.nextToken());
			C = Integer.parseInt(st.nextToken());
			I = Integer.parseInt(st.nextToken());
			
			// 명령어, 입력 문자열, 입력 문자열 위치
			commands = in.readLine();
			inputs = in.readLine();
			input = 0;
			
			memory = new int[M];

			pointer = 0;
			
			// 모든 괄호를 묶어준다.
			loops = getLoops();
			
			// 명령어 위치 i , 명령어 수행 횟수 cnt
			int cnt = 0;
			int i = 0;
			
			// 명령어 위치가 마지막에 도달하거나 cnt가 5천만번 수행하면 반복문 종료
			while(i < C && cnt < 50_000_000) {
				// 현재 명령어
				char command = commands.charAt(i);
				
				switch(command) {
				// 포인터에 해당하는 메모리의 값을 변경
				case '-':
					if(memory[pointer] == 0)
						memory[pointer] = 255;
					else
						memory[pointer]--;
					break;
				case '+':
					if(memory[pointer] == 255)
						memory[pointer] = 0;
					else
						memory[pointer] = memory[pointer]+1;
					break;
				// 포인터의 위치를 변경
				case '<':
					pointer--;
					if(pointer == -1)
						pointer = M-1;
					break;
				case '>':
					pointer++;
					if(pointer == M)
						pointer = 0;
					break;
				// 괄호의 조건에 맞으면 괄호의 짝의 위치로 이동
				case '[':
					if(memory[pointer] == 0)
						i = loops[i];
					break;
				case ']':
					if(memory[pointer] != 0)
						i = loops[i];
					break;
				// 문자열을 입력받기
				case ',':
					if(input == I)
						memory[pointer] = 255;
					else
						memory[pointer] = inputs.charAt(input++);
					break;
				}
				
				cnt++;
				i++;
			}
			
			// 모든 명령어를 수행 했다면
			if(i == C)
				sb.append("Terminates");
			// 무한 루프에 빠짐
			else {
				
				cnt = 0;
				
				// 방문하는 제일 큰 괄호와 제일 작은 괄호
				int max = i;
				int min = i;
				
				// 다시한번 5천만번 반복하면서 가장 오른쪽 위치와 가장 왼쪽 위치 저장
				while(i < C && cnt < 50_000_000) {
					char command = commands.charAt(i);
					
					min = Math.min(min, i);
					max = Math.max(max, i);
					
					switch(command) {
					case '-':
						if(memory[pointer] == 0)
							memory[pointer] = 255;
						else
							memory[pointer]--;
						break;
					case '+':
						if(memory[pointer] == 255)
							memory[pointer] = 0;
						else
							memory[pointer]++;
						break;
					case '<':
						pointer--;
						if(pointer == -1)
							pointer = M-1;
						break;
					case '>':
						pointer++;
						if(pointer == M)
							pointer = 0;
						break;
					case '[':
						if(memory[pointer] == 0)
							i = loops[i];
						break;
					case ']':
						if(memory[pointer] != 0)
							i = loops[i];
						break;
					case ',':
						if(input == I)
							memory[pointer] = 255;
						else
							memory[pointer] = inputs.charAt(input++);
						break;
					}
					
					cnt++;
					i++;
				}
				
				sb.append("Loops " + (min-1) + " " + max);
			}
			
			sb.append("\n");
		}
		
		out.write(sb.toString());
		out.flush();
	}
	
	// 괄호들을 묶어줌
	private static int[] getLoops() {
		int[] result = new int[C];
		
		Stack<Integer> stack = new Stack<>();
		
		for(int i = 0; i < C; i++) {
			if(commands.charAt(i) == '[')
				stack.push(i);
			else if(commands.charAt(i) == ']') {
				result[i] = stack.peek();
				result[stack.pop()] = i;
			}
		}
		
		return result;
	}
}

참고

---

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