팰린드롬의 경우의 수 질문드립니다.

자바 코딩테스트 - it 대기업 유제

4. "팰린드롬의 경우수" 문제 해법

작성

467

저는 입력값이 크지가 않아서 가능한 문자열의 길이가 n이 되면 팰린드롬을 체크해서 중복방지를 위해 해시셋에 만족하는 문자열을 담는 걸로 구현을 했습니다.

근데 재귀함수 안에서는 출력값이 잘 나오는거 같은데, 그걸 해시에 담았는데, 해시의 크기가 0으로 나옵니다. 무엇이 잘못된건가요???

import java.util.*;

class Main {
	public static boolean[] visit;
	public static int n;
	public static String[] ll;
	public static HashSet<String> ans = new HashSet<>();
	public String[] solution(String s){
		String[] answer = {};
		
		dfs(0,"");
		n=s.length();
		visit = new boolean[n];
		ll = s.split(""); //s를 문자열 배열로 분리
		ans = new HashSet<>();
		answer = new String[ans.size()];
		System.out.print(answer.length);
		return answer;
	}

	public static void dfs(int L, String str) { //문자열 만들어주기
		if(L==n) {
			if(check(str)) { //팰린드롬인지 체크
				//System.out.println(str);
				ans.add(str);
			}
			else return;
		}
		else {
			for(int i=0; i<ll.length;i++) { //i번째 문자 썼는지 확인하면서 문자열 만들어주기
				if(!visit[i]) {
					visit[i] = true;
					dfs(L+1,str+ll[i]);
					visit[i] = false;
				}
			}
		}
	}
	
	public static boolean check(String str) { //팰린드롬인지 체크
		String[] list = str.split("");
		
		int lt=0;
		int rt= list.length-1;
		while(lt<rt) {
			if(list[lt].equals(list[rt])) {
				lt++;
				rt--;
			}
			else return false;
		}
		return true;
	}
	public static void main(String[] args){
		Main T = new Main();
		System.out.println(Arrays.toString(T.solution("aaaabb")));	
		System.out.println(Arrays.toString(T.solution("abbcc")));
		System.out.println(Arrays.toString(T.solution("abbccee")));
		System.out.println(Arrays.toString(T.solution("abbcceee")));
		System.out.println(Arrays.toString(T.solution("ffeffaae")));
	}

}

java 코딩-테스트

답변 2

김태원

지식공유자

안녕하세요^^

최초의 DFS 호출의 위치가 잘못되었습니다. dfs(0,""); 의 위치를 해시셋을 생성한 후로 옮겨야 합니다.

인프런 AI 인턴

안녕하세요, 인프런 AI 인턴입니다.

해시셋에 문자열을 추가하는 부분에서 문제가 발생하는 것 같습니다. dfs 함수에서 문자열을 만들고, 팰린드롬인 경우에만 ans HashSet에 문자열을 추가하는데, 이 작업이 solution 함수 내에서 이루어져야 합니다. 현재는 dfs 함수를 호출하고 나서 초기화를 할 수 없는 문제가 있습니다.

해결 방법으로는 solution 함수 내에서 dfs 함수를 호출해 문자열을 만든 다음, dfs 함수에서 ans HashSet에 문자열을 추가하지 않도록 하고, solution 함수의 마지막에서 HashSet을 String 배열로 변환하는 작업을 추가하면 됩니다. 다음은 수정된 코드입니다.

import java.util.*;

class Main {
public static boolean[] visit;
public static int n;
public static String[] ll;
public static HashSet ans = new HashSet<>();
public String[] solution(String s){
String[] answer = {};

	n=s.length();
	visit = new boolean[n];
	ll = s.split(""); //s를 문자열 배열로 분리
	dfs(0,"");

	answer = ans.toArray(new String[ans.size()]);
	System.out.print(answer.length);
	return answer;
}

public static void dfs(int L, String str) { //문자열 만들어주기
	if(L==n) {
		if(check(str)) { //팰린드롬인지 체크
			//System.out.println(str);
			ans.add(str);
		}
		else return;
	}
	else {
		for(int i=0; i<ll.length;i++) { //i번째 문자 썼는지 확인하면서 문자열 만들어주기
			if(!visit[i]) {
				visit[i] = true;
				dfs(L+1,str+ll[i]);
				visit[i] = false;
			}
		}
	}
}

public static boolean check(String str) { //팰린드롬인지 체크하는 함수
	int len = str.length();
	for(int i=0; i<len/2; i++) {
		if(str.charAt(i)!=str.charAt(len-i-1)) return false;
	}
	return true;
}

}

수정된 코드에서는 dfs 함수를 먼저 호출하여 ans HashSet에 모든 가능한 팰린드롬 문자열을 추가하고, solution 함수의 마지막에서 ans HashSet을 String 배열로 변환합니다. 이렇게 수정하면 해결할 수 있을 것입니다.

수고하셨습니다.

인프런 커뮤니티 질문&답변

팰린드롬의 경우의 수 질문드립니다.