Ciphertext

혼자 힘으로 풀기 - 복기

메모리 초과 오류 : 과도한 재귀호출로 인해 스택 사용량이 초과 되어 메모리가 초과되었을 가능성이 높다.

• 메모리상에서 재귀호출과 스택과 힙

https://app.gitbook.com/@heunnajo/s/java/collection-framework/stackoverflowerror

실제로 디버깅을 해봤을 때도 동일한 문자열들이 처리되는 것을 확인할 수 있다.

		for(int k=index;k<c;k++) {
			//1.현재 index번째 문자를 선택하는 경우!
			go(k+1,s+input[k]);//다음 문자는 index+1번째부터 고르고, i+1번째에 채운다.
			//2.현재 index번째 문자를 선택하지 않는 경우!
			go(k+1,s);//index+1문자를 i번째에 선택, index번째 문자는 선택X이므로 s만 넘겨줌.
		}

왜 중복되는 문자열들이 나올 수밖에 없을까?

1번. 선택하는 경우에서 처리했던 문자열이라도 2번. 선택하지 않은 경우에서 다시 도돌이표처럼 이전의 1번.선택하는 경우가 다시 처리될 수 있다. 1번과 2번의 차이점은 s에 k번째 문장열을 붙이느냐 안 붙이느냐의 차이뿐이다. 1번에서 실행되었더라도 2번에서 재귀호출하면 동일하게 반복한다.

k for문을 돌면, 선택한 경우든 선택하지 않은 경우든 동일한 인덱스 k에 대해 동일한 문자열을 중복처리하게 된다!

Solution

k for문을 재귀함수 내에 돌리지 말고, 어차피 매개변수 index는 c-1까지 돌고, 한번씩만 돌면 되니까 index로 문자열을 하나씩 추가/추가X 처리한다.