[알고리즘] 자바에서의 재귀 호출(Recursive Call) # 2

다음과 같은 문제를 살펴보자.

https://www.acmicpc.net/problem/18511

18511번: 큰 수 구성하기

 

문제의 설명을 보면 제시되는 숫자 N 과 1 ~ 9 까지의 숫자가 1개 에서 최대 3개 까지 저장되는 집합 K 가 주어질 때,

K 집합 내부에 들어있는 원소들만으로 만들수 있는 숫자들 중에서 숫자 N 이하의 최대값을 찾으라고 되어 있다.

 

알고리즘 분류를 보면 무식하게 모든 경우의 수를 다 뒤져보는 완전 탐색 알고리즘인 브루트 포스(Brute Force) 알고리즘과 재귀라고 적혀있다.

 

미리 말해두자면, 조금 오래 걸렸지만 문제를 풀고 나서 다른 사람의 코드를 확인 해보니 아직 공부하지 않은 깊이 우선탐색(DFS) 알고리즘을 이용해서 굉장히 빠른 성능을 내는 코드를 작성하여 해결한 사람도 있었다.

(진짜 그 코드 보고 정신 나가는줄 알았다. 아직 내가 안 배운 알고리즘을 사용하면 훨씬 쉽고 빠르게 풀 수 있었다니)

게다가 결과적으로 애초에 목표였던 '재귀를 활용한 문제 해결' 에는 실패했다. 

 

물론 DFS 를 사용할 줄 알았다면 재귀 호출을 이용할 수 있었겠지만 나는 아직 DFS 를 배우지 않은 상태이기 때문에 처음에 생각한 로직 대로 재귀 호출을 하자 다음과 같은 오류를 마주 했다.

(백준에서는 당연히 메모리 초과라는 결과를 돌려줬다.)

 

Exception in thread "main" java.lang.StackOverflowError

 

이 때 당시 내가 작성한 코드를 한번 보자.

- Main.java

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
	
	private static String limitStr = "";
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int n = Integer.parseInt(st.nextToken());
		int kLength = Integer.parseInt(st.nextToken());
		
		int[] k = new int[kLength];
		
		st = new StringTokenizer(br.readLine(), " ");
		for(int i = 0; i < k.length; i++) {
			k[i] = Integer.parseInt(st.nextToken());
		}
		
		int number = 0;
		int[] limitArray = new int[10-k.length];
		for(int i = 0; i < limitArray.length; i++) {
			boolean match = false;
			for(int index = 0; index < k.length; index++) {
				if(number == k[index]) {
					match = true;
					break;
				}		
			}
			if(!match)
				limitArray[i] = number;
			else
				i--;
			
			number++;
		}
	
		for(int i = 0; i < limitArray.length; i++) {
			limitStr += String.valueOf(limitArray[i]);
		}
		
		bw.write(bigNumber(n) + "\n");
		bw.flush();
		bw.close();
		
	}

	private static int bigNumber(int n) {
		String str = String.valueOf(n);
		boolean contain = false;
		for(int i = 0; i < limitStr.length(); i++) {
			if(str.contains(String.valueOf(limitStr.charAt(i)))) {
				contain = true;
				break;
			}
		}
		
		if(contain)
			return bigNumber(n-1);
		else
			return n;	
	}
}

- 숫자 N, 집합 K 를 입력 받은 다음 집합 K 의 경우 0 ~ 9 까지의 숫자 중에 K 집합에 속하지 않는 숫자를 찾아서 limitArray 배열에 적재하였다.

- 이후 재귀 호출 메소드에 파라미터 값으로 배열 자체를 주는것을 방지하기 위해(메모리를 아껴야 했다.) 미리 static 변수로 선언해둔 limitStr 문자열에 해당 배열을 하나씩 추가해주어 문자열 형태로 제한되는 숫자들을 묶어주었다.

- 그 다음부터 본격적으로 재귀 호출을 시작하였다.

 

- 재귀로 호출되는 bigNumber 메소드 에서는 숫자 N 을 파라미터로 받아서 문자열로 형반환을 해준 이후 반복문 내부에서 contain 메소드를 활용해 limitStr 의 특정 인덱스가 문자열로 형변환한 숫자 N 에 포함되는 경우 조건을 만족하지 않는것이므로 반복문을 종료시켰다.

- 이후 반복문의 결과가 어떻게 되느냐에 따라 숫자 N 에서 1을 뺀 값을 파라미터로 재귀 호출을 해주거나, 숫자 N 자체를 반환해주었다.

 

위와 같이 작성했더니 앞서 보여줬던 것처럼 StackOverflow 에러가 발생했다.

 

메소드를 재귀 호출할 경우 메소드에서 사용되는 지역 변수들이 JVM 메모리의 스택 영역에 쌓인다.

자바에서 메소드를 재귀 호출하면 해당 실행 프로세스가 스택 처럼 쌓여서 실행되듯이, 메소드의 매개변수 및 지역변수 들은 JVM 에서 스택 영역에 쌓이게 된다.

자세한 내용은 아래의 링크를 참조하자.

https://velog.io/@woo00oo/JVM%EC%9E%90%EB%B0%94-%EA%B0%80%EC%83%81-%EB%A8%B8%EC%8B%A0

JVM(자바 가상 머신)

 

* 결론적으로 말하자면, 메소드를 재귀 호출하면서 해당 호출 횟수가 일정 이상을 넘어갈 경우, 메소드의 지역 변수와 같은 정보들이 JVM 의 스택영역에 그만큼 쌓여가다가 결국 한계를 맞닥뜨리게 되어 StackOverflow 가 발생하게 되는 것이다.

 

이를 확인하기 위해 위의 코드에 다음과 같이 재귀 함수 호출 횟수를 확인할 수 있는 로그 출력용 코드를 작성하였다.

- Main.java

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class BigNumberConfig {
	
	private static String limitStr = "";
	private static int count = 0; // 재귀 함수에서도 사용할 수 있게 전역변수 설정
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int n = Integer.parseInt(st.nextToken());
		int kLength = Integer.parseInt(st.nextToken());
		
		int[] k = new int[kLength];
		
		st = new StringTokenizer(br.readLine(), " ");
		for(int i = 0; i < k.length; i++) {
			k[i] = Integer.parseInt(st.nextToken());
		}
		
		int number = 0;
		int[] limitArray = new int[10-k.length];
		for(int i = 0; i < limitArray.length; i++) {
			boolean match = false;
			for(int index = 0; index < k.length; index++) {
				if(number == k[index]) {
					match = true;
					break;
				}		
			}
			if(!match)
				limitArray[i] = number;
			else
				i--;
			
			number++;
		}
	
		for(int i = 0; i < limitArray.length; i++) {
			limitStr += String.valueOf(limitArray[i]);
		}
		
		bw.write(bigNumber(n) + "\n");
		bw.flush();
		bw.close();
		
	}

	private static int bigNumber(int n) {
		count++; // 재귀 함수 호출 때마다 값 증가
		System.out.println("재귀 호출 횟수 : " + count); // 출력
		String str = String.valueOf(n);
		boolean contain = false;
		for(int i = 0; i < limitStr.length(); i++) {
			if(str.contains(String.valueOf(limitStr.charAt(i)))) {
				contain = true;
				break;
			}
		}
		
		if(contain)
			return bigNumber(n-1);
		else
			return n;	
	}
}

 

 

위와 같이 코드를 작성하고 숫자 N 의 값으로 문제에서의 최대값인 1,000,000,00 (1억) 과 집합 배열 길이 3,

집합의 구성요소로 1, 5, 7 을 주고 실행 결과를 봤더니 아래와 같이 나온것을 확인할 수 있었다.

 

.....
재귀 호출 횟수 : 4789
재귀 호출 횟수 : 4790
재귀 호출 횟수 : 4791
재귀 호출 횟수 : 4792
Exception in thread "main" java.lang.StackOverflowError

 

출력된 로그를 보면 대략 4793번째 재귀 호출에서 더 이상 메모리가 공간을 할당해 주지 못하고 StackOverflow 를 발생시킨것을 확인해 볼 수 있다.

여기서 몇번을 더 실행해봐도 4780 번째 언저리에서 크게 벗어나지 않았다.

 

재귀 호출을 할 때마다 해당 함수의 매개변수와, 내부에서 선언된 지역 변수들이 메모리에서 사라지지 않고 대략 4780번 을 새롭게 메모리에 공간을 할당 받으니 더 이상 새로 할당해줄 공간이 남지 않게 되는것은 필연적인 것인지도 모르겠다.

 

그래서 결국 코드를 아래와 같이 고쳐주었다.

고쳐 주는 과정에서 숫자에 대한 검증을 K 집합에 속하지 않는 숫자들을 대상으로 하는게 아닌, 집합에 속해있는 숫자들 자체를 대상으로 검증하는 것으로 하여 그나마 실행시간을 줄였다.

(기존 1회 반복당 최대 검증횟수 9회, 최소 7회 -> 최대 3회, 최소 1회)

(3중첩 반복문을 사용한 것이 정말 마음에 들지 않는다;;)

 

- Main.java 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int n = Integer.parseInt(st.nextToken());
		int kLength = Integer.parseInt(st.nextToken());
		
		int[] k = new int[kLength];
		
		st = new StringTokenizer(br.readLine(), " ");
		for(int i = 0; i < k.length; i++) {
			k[i] = Integer.parseInt(st.nextToken());
        }
		
		while(true) {
			String str = String.valueOf(n);
			boolean contain = true;
			for(int i = 0; i < str.length(); i++) {
				boolean match = false;
				for(int index = 0; index < k.length; index++) {
					if(str.charAt(i) == Character.forDigit(k[index], 10)) {
						match = true;
						break;
					}
				}	
				
				if(!match) {
					contain = false;
					n--;
					break;
				}
			}
			if(contain)
				break;		
		}
		bw.write(n + "\n");
		bw.flush();
		bw.close();
	}
}

 

위와 같이 작성해주니 1992 ms 라는 어마어마한 실행시간을 기록한 채 문제를 통과할 수 있었다.

(그리고 DFS 알고리즘을 작성하여 해당 메소드를 재귀적으로 호출한 사람의 실행 시간은 120ms ~ 220ms..... 거의 13배 ~ 15배 차이...)

 

다른 사람들이 아직 내가 공부하지 않은 알고리즘을 이용해 문제를 쉽게 풀어내는 것을 보고 있자니, 알고리즘에 대한 공부 욕구에 더 샘솟는 것 같다.