글 읽기 - OutOfMemoryError 문제 어떻게 해결하면 좋을까요 ㅠㅠ

0702leesj 4년 전 0

다 long으로 바꿨고,

ArrayList가 버티질 못하기에 HashMap으로 바꿔주었습니다.

그런데 질문게시판을 보던중에

100000000
5
100000000 L
100000000 L
200000000 L
199999999 L
199999999 L

이 예시를 보게 되어 돌렸더니,

Exception in thread "main"
Exception: java.lang.OutOfMemoryError thrown from the UncaughtExceptionHandler in thread "main"

에러가 뜹니다 ㅠㅠ 어떻게 해결해야할지 감이 안오는데

도와주실 천사분 계실까요...ㅠㅠ

다른 작은 케이스들은 다 답이 맞게 나오는 것 같아요!

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {
	static long seconds;
	static int head;
	static Snake snakehead;
	static long L;
	static HashMap<String,Integer> hm;
	
	public static void rotate(String S) {
		if (S.equals("R")) {
			if (head == 1) {
				head = 3;
			} else if (head == 2) {
				head = 4;
			} else if (head == 3) {
				head = 2;
			} else {
				head = 1;
			}
		} else if (S.equals("L")) {
			if (head == 1) {
				head = 4;
			} else if (head == 2) {
				head = 3;
			} else if (head == 3) {
				head = 1;
			} else {
				head = 2;
			}
		}
	}

	public static int go() {
		long x = 0, y = 0;
		x = snakehead.getX();
		y = snakehead.getY();
		
		if (head == 1) {
			y++;
		} else if (head == 2) {
			y--;
		} else if (head == 3) {
			x++;
		} else if (head == 4) {
			x--;
		}
		if (x < 0 || x >= 2*L+1 || y < 0 || y >= 2*L+1) { // 벽을 만난 경우
			return -1;
		}
		if (hm.containsKey(x+","+y)) { // 몸이랑 만난경우
			return -1;
		}
		snakehead = new Snake(x, y); // 추가
		hm.put(x+","+y, 1);
		return 0;
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		L = Long.parseLong(sc.nextLine());

		hm = new HashMap<String,Integer>();
		
		seconds = 0;
		head = 1; // right

		long N = Long.parseLong(sc.nextLine()); // 뱀의 방향변환 횟수
		ArrayList<Command> clist = new ArrayList<Command>();
		snakehead = new Snake(L,L);
		hm.put(L+","+L, 1);
		
		for (long i = 0; i < N; i++) {
			StringTokenizer st2 = new StringTokenizer(sc.nextLine(), " ");
			long X = Integer.parseInt(st2.nextToken());
			String C = st2.nextToken();
			clist.add(new Command(X, C));
		}
		

		int flag = 0;
		long time;
		while(true){
			long count = 0;
			if(clist.size()==0)
				time = Long.MAX_VALUE;
			else
				time=clist.get(0).getTime();
		
			while(count != time){
				count++;
				seconds++;
				int result = go();
				if (result == -1) {
					System.out.print(seconds);
					flag = 1;
					break;
				}
			}
			if(flag == 1){
				break;
			}
			rotate(clist.get(0).getcommand());
			clist.remove(0);
		}
	}
}

class Snake {
	private long x;
	private long y;

	public Snake(long l, long l2) {
		this.x = l;
		this.y = l2;
	}

	public long getX() {
		return this.x;
	}

	public long getY() {
		return this.y;
	}
}

class Command {
	private long time;
	private String command;

	public Command(long X, String C) {
		this.time = X;
		this.command = C;
	}

	public long getTime() {
		return this.time;
	}

	public String getcommand() {
		return this.command;
	}

}

bupjae 4년 전 0

이 알고리즘대로라면 첫 번째 Command를 처리하는데만 해도 필요한 메모리의 양이 100000000 * (8+8) = 약 1.5GB 입니다.

(단, 이 계산은 Snake 를 그대로 HashMap에 저장하는 것으로 가정했습니다. 지금과 같이 String으로 변환한 뒤 HashMap에 저장하게 된다면 실제로는 더 많은 용량이 필요할 가능성이 큽니다)

이 문제의 핵심은 뱀의 이동 경로를 저장할 자료구조를 고안하는 것입니다. 한칸 한칸 저장해서는 메모리 초과를 피할 수 없습니다.

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

문제

문제

출처

ICPC

OutOfMemoryError 문제 어떻게 해결하면 좋을까요 ㅠㅠ

0702leesj 4년 전 0

bupjae 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말