글 읽기 - 반례가 있을까요?

howcatchem 2년 전 0

방문한 괄호 중 가장 오른쪽에 있는 값을 구했다가, 바깥쪽 루프를 돌다가 안쪽에서 무한 루프에 갇히는 경우가 있을 수 있다고 해서 5000만번을 넘어가면 메모리를 0으로 초기화하고 다시 5천만번, 즉 1억번을 돌려서 닫는 괄호의 인덱스 값을 구했습니다

예제와 질문 게시판에 있는 input들도 전부 맞았는데 어디가 틀렸는지 모르겠습니다 도와주세요ㅜㅜ

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

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int T = Integer.parseInt(br.readLine());
		
		test: for(int tc = 0; tc<T; tc++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int m = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			int i = Integer.parseInt(st.nextToken());
			
			int[] arr = new int[m];
			char[] code = new char[c];
			int[] bracket = new int[c];
			Stack<Integer> stack = new Stack<>();
			
			String str = br.readLine();
			for(int k = 0; k<c; k++) {
				code[k] = str.charAt(k);
				if(code[k]=='[') stack.push(k);
				else if(code[k]==']') {
					int tmp = stack.pop();
			        bracket[k] = tmp;
			        bracket[tmp] = k;
				}
			}
			
			st = new StringTokenizer(br.readLine());
			
			int pointer = 0; // 배열의 포인터값
			int codeIndex = 0; // 코드의 인덱스값
			int memory = 0; // 메모리
			int close = 0;
			boolean loop = false;
			
			while(true) {
				if(!loop && codeIndex==c) {
					sb.append("Terminates\n");
					continue test;
				} else if(memory>50000000) {
					if(!loop) {
						memory = 0;
						loop = true;
					} else break;
				}
				
				switch(code[codeIndex]) {
					case '-':
						arr[pointer] = (arr[pointer]-1)%256;
						break;
					case '+':
						arr[pointer] = (arr[pointer]+1)%256;
						break;
					case '<':
						pointer = (pointer+m-1)%m;
						break;
					case '>':
						pointer = (pointer+1)%m;
						break;
					case '[':
						if(arr[pointer]==0) codeIndex = bracket[codeIndex];
						break;
					case ']':
						if(loop && close < codeIndex) close = codeIndex;
						if(arr[pointer]!=0) codeIndex = bracket[codeIndex];
						break;
					case '.':
						break;
					case ',':
						if(!st.hasMoreTokens()) arr[pointer] = 255;
						else arr[pointer] = st.nextToken().charAt(0);
						break;
				}
				
				codeIndex++;
				memory++;
			}
			
			sb.append("Loops " + bracket[close] + " " + close + "\n");
			
		}
		
		System.out.println(sb);

	}

}

horsedrinkscoffee 1년 전 2

제가 아직 반례 만들 정도로 똑똑하지 않아서, 속시원한 답이 될지는 모르겠지만, 한번 적어봅니다!

메모리를 초기화하고 close값을 찾을 때 가장 안쪽에 있는 닫는 괄호를 찾게 되는데 논리적으로 이런 문제가 있을 것 같습니다.

루프가 5천만번이 애매한 위치에서 끝났을 때 잘못된 괄호를 구하게 됩니다.

[(실제 무한루프 시작)..............[............(5천만번째 끝)..........](가장 작은 닫는 괄호, 이걸 답으로 할듯)................](실제 무한루프 끝..)

--> 그래서 5천만번 더 돌릴 때는 오히려 닫는 괄호의 가장 큰 인덱스를 찾으면 되지 않을까 싶습니다!! 어차피 무한루프에 걸려있으니 5천만번 이내에 갈 수 있는 최대한의 닫는 괄호가 최종 루프일 것 같습니다.

GCPC 들어가서 찾은 도움이 될지 모르는 반례인데 한번 참고해보세요.

input:

20 257 1
+[>>>>>>>++++++>>>+>>>>+[-<<<<>+<[-<<<<<<<<+<[>>>>>>>>>>>>+<<<<<<<<<<<-]>[->>>>>>>>+<<<<<<<]<<->>>>>>>>>>-]>[->]<<>+<[-<<<<<+<[>>>>>>>>>+<<<<<<<<-]>[->>>>>+<<<<]<<->>>>>>>-]>[->]<<>+<[-<<+<[>>>>>>+<<<<<-]>[->>+<]<<->>>>-]>[->]<<+>>>[[-]>+<]>]<<<<<<<<<<<<<<]
a

output:

Loop 1 256

댓글을 작성하려면 로그인해야 합니다.