[코딩연습] 최대 자리곱(구름-3단계) - Error(시간초과)

 

 

풀이과정 (아래 글과 스크린샷을 참고해주세요.)

 

풀이의 버젼은 4개로 되어있으며

1~3 버전까지는 readline()으로 읽은 문자열을 정수로 형변환 후 for 반복문을 만들고 다시 개별 숫자를 문자열로 변환하여 charAt()메소드를 활용하는 방식으로 값을 구하였습니다.

 

4버젼 부터 정수로 형변환 후 사칙연산만을 통해 값을 구하였습니다.

 

입력정수값 N이 10억(테스트케이스 3번)의 연산시간은 점차 줄어들었으나 결국 해결하지는 못하였습니다.

 

(코드는 아래 [풀이방식 ver1~3 / 풀이방식 ver4]에 작성되었습니다.)

 

 

---

문제를 읽고 예상했던 것보다 훨씬 더 많은 시간을 투입했지만 해결하지 못한 문제입니다.

(풀이방법을 아시는분은 공유해주시면 감사하겠습니다. ㅠㅠ)

문제를 풀기위해 방법을 달리하여 시도한 클래스 리스트

 

 

First : 배열  / ArrayList 

 

 ArrayList를 활용하여 숫자들을 관리하여 문제해결 시도

   -> 배열의 경우 요소의 갯수가 억단위를 넘어가면 에러(OutOfMemoryError)가 발생 합니다. (약 3~4억 이상)

 

 

 

Second : 리스트에 자릿수 곱 값을 추가한 뒤 해당 값을 매번 다음 숫자와 비교 후 큰값으로 변경

Third : 별도의 리스트 생성없이 계산 값 비교 후 변경 

 

 모든 수를 배열로 관리할 수 없기 때문에 숫자의 자리곱을 구할 때마다 크기를 비교하여 큰 수를 저장하였다가 출력

  -> 이때부터는 시간초과에러가 발생했습니다.

 

 

4th : 10을 기준으로 자릿수 곱 계산

 

이전까지 숫자를 정수로 변환하고 문자열로 다시 변환하는 과정을 거쳤지만 사칙연산만을 통해 숫자의 자리곱을 구하기 시작했습니다. 

 -> 여전히 시간초과에러 발생

 

 10억(테스트케이스 3번)의 자리곱값 중 가장 큰 값을 구하는 시간을 점차 줄일 수 있었지만 개인적으로 더이상 방법을 찾지못하여 포기하게 되었습니다.

(System.nanoTime()메소드를 활용하여 결과값이 나오는 시간을 계산.)

 

 

시간초과 때문에 통과하지 못하지만 아래 콘솔창의 값 387420489은 아래 예상출력값과 같습니다.

 

  

---

 

 

풀이방식 ver1 ~ 3

//[입력 문자열 > 정수 > 문자열 ] 풀이방식

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int input = Integer.parseInt(br.readLine());
		ArrayList<Integer> arrN = new ArrayList<Integer>();
		
		int times = 0, result = 0;
		arrN.add(times);
		
		for(int i=1; i<=input; i++) {
			times=1;
			String str = Integer.toString(i);
			for(int j=0; j<str.length(); j++) {
				times *= (str.charAt(j)-'0');
			}
			if(times <= result) continue;
			
			result = times;
		}
		
		System.out.println(result);

 

풀이방식 ver 4

//[입력 문자열 > 정수 > 사칙연산] 풀이방식

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int input = Integer.parseInt(br.readLine());
		long result=0l;
		
		
		for(int i=1; i<=input ; i++) {
			
			long times=1; 
			int num=i;
			
			while(num != 0) {
				times *= (num%10);
				num /= 10;
			}
			
			if(times<=result) continue;
			result=times;
		}
		
		System.out.println(result);

 

 

 

 

 

 

---

<참고>

 

https://www.crocus.co.kr/399

숫자의 각 자릿수 구하기 알고리즘

https://stackoverflow.com/questions/19313294/java-lang-outofmemoryerror-java-heap-space-while-initialising-an-array

java.lang.OutOfMemoryError: Java heap space while initialising an array

https://sejoung.github.io/2019/03/2019-03-20-Understand_the_OutOfMemoryError_Exception/#Exception-in-thread-thread-name-java-lang-OutOfMemoryError-GC-Overhead-limit-exceeded

OutOfMemoryError Exception 의 이해 | 폭간의 기술블로그

 

https://docs.oracle.com/javase/8/docs/technotes/guides/troubleshoot/memleaks002.html

Understand the OutOfMemoryError Exception