글 읽기 - 메모리초과 조언 부탁드립니다.

dae9221 4년 전 0

안녕하세요.

아래와 같이 arraylist를 이용해서 코드를 짰는데요, 99%에서 메모리초과가 납니다.

3이나 2로 나눠지지 않을 때는 아무 것도 하지 않고 될 때 숫자들을 넣습니다. 이미 존재하는수는 넣지 않도록 하여 메모리를 많이 줄였다고 생각하는데 메모리 초과가 나네요..

arraylist를 사용하기 때문에 메모리 초과가 나는 건가요? 그냥 일반 배열을 쓰면 괜찮을까요?

import java.io.IOException;
import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	public static void main(String args[]) throws IOException {
		Scanner sc = new Scanner(System.in);
		int num = sc.nextInt();

		ArrayList<Integer> arr = new ArrayList<>();
		ArrayList<Integer> nextarr = new ArrayList<>();

		if (num % 3 == 0) {
			arr.add(num / 3);
		}
		if (num % 2 == 0) {
			arr.add(num / 2);
		}
		if (num - 1 > 0) {
			arr.add(num - 1);
		}
		int cnt = 1;
		if (arr.contains(1)) {
			System.out.println(cnt);
		} else {
			for (int i = 0; i < arr.size(); i++) {
				int getnum = arr.get(i);
				if (getnum % 3 == 0) {
					if (!nextarr.contains(getnum / 3)) {
						nextarr.add(getnum / 3);
					}
				}
				if (getnum % 2 == 0) {
					if (!nextarr.contains(getnum / 2)) {
						nextarr.add(getnum / 2);
					}
				}
				if (getnum - 1 > 0) {
					if (!nextarr.contains(getnum - 1)) {
						nextarr.add(getnum - 1);
					}
				}
			}
			cnt++;
			if (nextarr.contains(1)) {
				System.out.println(cnt);
			} else {
				while (true) {
					arr.clear();
					arr.addAll(nextarr);
					nextarr.clear();
					for (int i = 0; i < arr.size(); i++) {
						int getnum = arr.get(i);
						if (getnum % 3 == 0) {
							if (!nextarr.contains(getnum / 3)) {
								nextarr.add(getnum / 3);
							}
						}
						if (getnum % 2 == 0) {
							if (!nextarr.contains(getnum / 2)) {
								nextarr.add(getnum / 2);
							}
						}
						if (getnum - 1 > 0) {
							if (!nextarr.contains(getnum - 1)) {
								nextarr.add(getnum - 1);
							}
						}
					}
					cnt++;
					if (nextarr.contains(1)) {
						System.out.println(cnt);
						arr.clear();
						nextarr.clear();
						break;
					}
				}
			}
		}
		sc.close();
	}
}

rubix 4년 전 0

1을 넣을 때 무한루프를 돕니다.

dae9221 4년 전 0

아 크거나 같을 때 이군요..

1일 때 처리해주니 되네요.

감사합니다.

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

문제

문제

출처

ICPC

메모리초과 조언 부탁드립니다.

dae9221 4년 전 0

rubix 4년 전 0

dae9221 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말