글 읽기 - 2023 메모리 초과 질문

vision929 4년 전 0

처음에는 substring() 을 사용해서 메모리 초과가 된 것 같아 charAt() 으로 바꿨지만 메모리 초과 문제가 여전히 해결되지 않네요

아예 string 쪽이 문제인가 싶어서 int 형 그 자체에서 계속해서 자릿수별로 수를 가져와보는 것도 생각해보았습니다만.. 그건 또 시간초과 문제로 넘어가게 됩니다...

주석 처리한 부분이 String 을 사용하지 않고 int 만 사용한 부분입니다.

메모리 초과 문제 어떻게 해결해야 할까요?

package b_2023;

import java.util.Scanner;

public class Main {
	//https://www.acmicpc.net/problem/2023
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();
		int N = sc.nextInt();
		
		for (int i = (int) Math.pow(10, N - 1); i < (int) Math.pow(10, N); i++) {
//			if ((int) (i / Math.pow(10, N - 1) % 10) == 1 || (int) (i / Math.pow(10, N - 1) % 10) == 4 || (int) (i / Math.pow(10, N - 1) % 10) == 6 || (int) (i / Math.pow(10, N - 1) % 10) == 8)
//				continue;
//			if (i != 2 && i % 2 == 0)
//				continue;
			if(isTrue(i, 0, N))
				sb.append(i + "\n");
		}
		
		System.out.print(sb.toString());

	}
	
	public static boolean isTrue(int num, int len, int N) {		
		boolean isTrue = false;
		String strNum = "" + num;
		for (int i = 1; i <= N ; i++) {
			String strK = "";
			for (int j = 0; j < i; j++) {
				strK += strNum.charAt(j);
			}
			if (isPrime(Integer.parseInt(strK))) {
					isTrue = true;
			} else
				return false;
		}
		
		return isTrue;
		
//		int temp = 1;
//		int copyN = N;
//		while(copyN-- > 0) {
//			int k = 0;
//			int digit = N - 1;
//			for (int i = 1; i <= temp; i++) {
//				k *= 10;
//				if (digit == 0)
//					k += num % 10;
//				else 
//					k += num / Math.pow(10, digit) % 10;	
//				digit--;
//			}
//			
//			if (k == 1)
//				return false;
//			
//			if (k != 2 && k % 2 == 0)
//				return false;
//			
//			for (int i = 3; i <= Math.sqrt(k); i++) {
//				if (k % i == 0)
//					return false;
//			}
//			
//			temp++;
//		}
//		
//		return true;
		
	}
	
	public static boolean isPrime(int num) {
		if (num == 1)
			return false;
		for (int i = 2; i <= Math.sqrt(num); i++) {
			if (num % i == 0)
				return false;
			}
		return true;
	}

}

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

문제

문제

출처

ICPC

2023 메모리 초과 질문

vision929 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말