[백준, Back Tracking, JAVA] P.1342 행운의 문자열

예... 이번 문제도 나름의 아이디어를 써봤으나 메모리 초과로 다른 아이디어로 접근해서 해결했습니다.. 우선 문제 접근 자체는 크게 어렵지 않았습니다. 일단 이전에 제가 실패 했던 아이디어입니다.

1. 첫 번째 문자는 일단 아무거나 다 선택한다.

2. 현재 문자열의 길이가 초기값과 같은지?(완성 여부) 같으면 해당 값이 이미 있는지?

3. 두번째부터 문자를 선택한다

4. 2번째 문자부터 분기 조건을 부여하는데

   (1) 바로 직전 문자와 선택한 문자가 같으면 안됨

   (2) 이미 방문한 문자 위치면 안됨

5. 2번으로 다시 재귀 실행...

여기에서 2번을 제외하면 그냥 재귀함수랑 기본적인 분기처리를 그대로 따라가면서 짜면 됩니다. 하지만 2번을 구현하기 위해서는 이전에 완성된 문자열을 저장해주는 공간이 필요한데 저는 자료구조의 Set을 이용하였습니다. Set은 중복 저장이 안되기 때문에 2번의 내용을 추상적으로 모두 해결해 주기 때문입니다. 아래는 해당 코드입니다. 일부분은 생략하고 핵심 부분만 적었습니다.

	static Set<String> resultSet = new HashSet<String>();

	public static void findLuckyString(String s) {
		if (s.length() == strLen) {
			resultSet.add(s); // resultSet.size()가 정답이겠지?
		}

		for (int i = 0; i < strLen; i++) {
			if (visited[i])
				continue;
			if (s.charAt(s.length() - 1) == carr[i]) {
				continue;
			}
			visited[i] = true;
			findLuckyString(s + carr[i]);
			visited[i] = false;
		}
	}

정답은 맞습니다... 하지만 이렇게 하니까 메모리 초과가 발생하더군요 당연하겠지만 길이가 10이고 문자가 모두다른 abcdefghij 같은 문자열은 총 3628800개의 문자열이 저장됩니다. 뭔가 다른 아이디어가 필요하겠구나 생각이 들었습니다. 몇시간 고민해봤는데 순열이 생각나더라구요 똑같은 값들이 있을때 똑같은 문자의 갯수들의 factorial 값들을 결과값에 나누어 주면 되겠다고 생각했습니다.

그 결과는? 네 정답이었습니다! 트리를 이용한 아이디어를 생각해내서 뿌듯했다가 메모리 초과로 좌절했다가 다시 순열 아이디어로 간신히 풀었네요.. 아래에는 최종 코드입니다. 몇시간 잡아야 정답률 높은 문제의 아이디어가 나올까 말까 하군요ㅋㅋ
아직 멀었습니다.. 앞으로 몇년.. 아니 평생 계속 목표는 최고로 잡고 계속계속계속 할겁니다!!!

import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;

public class Main {
	static boolean[] visited;
	static String str;
	static int strLen;
	static int result = 0;
	static Set<String> resultSet = new HashSet<String>();
	static char[] carr;
	static Map<Character, Integer> map = new HashMap<>();

	public static void main(String[] args) {
		Scanner scr = new Scanner(System.in);

		str = scr.next();
		carr = str.toCharArray();
		strLen = str.length();
		visited = new boolean[strLen];

		// 문자를 저장하는 Map 똑같은 문자가 있으면 1을 더해준 뒤 replace 합니다.
		for (int i = 0; i < strLen; i++) {
			if (map.getOrDefault(carr[i], null) == null) {
				map.put(carr[i], 1);
			} else {
				int getValue = map.get(carr[i]);
				map.replace(carr[i], getValue + 1);
			}
		}

		for (int i = 0; i < strLen; i++) {
			visited[i] = true;
			findLuckyString("" + carr[i]);
			visited[i] = false;
		}

		// 같은 문자들을 Factorial 연산을 통해 결과값에 나누어 주는 코드 부분
		Iterator<Character> itr = map.keySet().iterator();
		while (itr.hasNext()) {
			char value = itr.next();
			int v = map.get(value);
			int factorial = 1;
			for (int i = 1; i <= v; i++) {
				factorial *= i;
			}

			result /= factorial;
		}

		System.out.println(result);
	}

	public static void findLuckyString(String s) {
		if (s.length() == strLen) {
			result++;
		}

		for (int i = 0; i < strLen; i++) {
			if (visited[i])
				continue;
			if (s.charAt(s.length() - 1) == carr[i]) {
				continue;
			}
			visited[i] = true;
			findLuckyString(s + carr[i]);
			visited[i] = false;
		}
	}
}