글 읽기 - 런타임 에러...

jihea37 7년 전 0

방문한 것을 ArrayList로 했더니 시간초과가 나서

boolean 배열로 바꿨는데요.

런타임에러가 납니다.

왜그런건가요?

boolean[] visited = new boolean[10000]; 이 부분을 어떤 방식으로 해야할지 모르겠어요.

해시맵으로 해봤지만 시간초과였습니다.ㅠㅠ

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Scanner;

class Node {
	int num;
	String type;

	public Node(int num, String type) {
		this.num = num;
		this.type = type;

	}
}

class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();

		LinkedList<Node> queue = new LinkedList<Node>();
//		ArrayList<Integer> mem = new ArrayList<Integer>();
		boolean[] visited = new boolean[10000];

		for (int i = 0; i < n; i++) {

			int start = sc.nextInt();
			int fin = sc.nextInt();
			//
			// int start=1000;
			// int fin=1;

			queue.clear();
//			mem.clear();
			for(int j=0; j<10000; j++){
				visited[j]=false;
			}

			queue.addLast(new Node(start, ""));
//			mem.add(start);
			visited[start]=true;

			while (!queue.isEmpty()) {
				Node now = queue.poll();

				if (now.num == fin) {
					System.out.println(now.type);
					break;
				}

				int d = (now.num * 2) % 10000;
				int s = (now.num - 1);
				if (s == 0) {
					s = 9999;
				}
				int tmp1 = now.num / 1000;
				int l = (now.num - (tmp1 * 1000)) * 10 + tmp1;
				int tmp2 = now.num % 10;
				int r = (now.num / 10) + (tmp2 * 1000);

				if (visited[d]==false) {
					queue.addLast(new Node(d, now.type + "D"));
					visited[d]=true;
//					mem.add(d);
					// System.out.println(d +" = " + now.type+"D");
				}
				if (visited[s]==false) {
					queue.addLast(new Node(s, now.type + "S"));
					visited[s]=true;
//					mem.add(s);
					// System.out.println(s +" = " + now.type+"S");
				}
				if (visited[l]==false) {
					queue.addLast(new Node(l, now.type + "L"));
					visited[l]=true;
//					mem.add(l);
					// System.out.println(l +" = " + now.type+"L");
				}
				if (visited[r]==false) {
					queue.addLast(new Node(r, now.type + "R"));
					visited[r]=true;
//					mem.add(r);
					// System.out.println(r +" = " + now.type+"R");
				}

			}

		}

	}

}

koosaga 7년 전 0

노드 하나가 공간을 n 먹어서 메모리 초과가 나는 것으로 추측됩니다.

팁 : 각각의 숫자에 대해서 parent를 저장해보세요. 해당 숫자를 도달하기 위해서 이전에 어떤 숫자에서, 어떤 연산을 사옹했는지 안다면, 연산의 역추적이 가능합니다.

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

문제

문제

출처

ICPC

런타임 에러...

jihea37 7년 전 0

koosaga 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말