코테 | 강의 - 깊이 우선 탐색 - DFS 섹션 - (2)

🟩 4번. 팰린드롬의 경우 수

문제 설명

풀이

• Deque 자료구조를 사용하여 팰린드롬 만들 것

1) 애초에 입력으로 들어온 String 구성이 팰린드롬을 만들 수 있는 구성인지 확인

       (1) 문자별 빈도수가 모두 짝수 → 팰린드롬 만들기 가능

       (2) 문자별 빈도수가 홀수인 경우 → 홀수인 문자 1개만 있으면 가능, 1개 이상이면 불가능

2) HashMap 사용하여 각 문자별 빈도수 체크

3) map을 keySet()으로 순회하면서 해당 키의 빈도수가 홀수인 문자를 odd변수로 카운팅한다.

4) 만약 odd > 1 이면 빈 String 배열을 곧장 리턴해준다. (팰린드롬 못 만들기 때문)

5) odd가 1개 or 0개여서 팰린드롬이 가능하다면. DFS() 시작

6) DFS에서는 Deque를 활용하여 각 깊이에서 순회할 수 있는 사이즈 0이 아닌 문자에 대하여 탐색하는데, 그때 앞, 뒤 모두 1개씩 담아주면서 빈도수도 빼주며 탐색한다.

7) 만약 Deque의 길이가 태초 입력으로 들어왔던 길이와 같아질 경우 ArrayList에 담아준다.

package to_0814_1;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;

//팰린드롬 경우 수 
class Solution {
	static Deque<Character> dq;
	static ArrayList<String> res;
	static HashMap<Character, Integer> map;
	static int len;
	
	//dfs
	static void DFS() {
		if(dq.size() == len) { //dq가 len길이만큼 완성되면 
			String Ts = "";
			for(char x : dq) Ts += x; 
			res.add(Ts);//리스트에 담음 - 답 복제용
		}else {
			//해쉬맵 순회하면서 
			for(char key : map.keySet()) {
				if(map.get(key) == 0) continue;//건너뜀
				//하나의 key에 대하여 
				//1) 앞에 담고 
				dq.addFirst(key);
				//2) 뒤에 담고
				dq.addLast(key);
				map.put(key, map.get(key)-2);//두 번 담았으니까 빼주고
				DFS();//재귀 호출 
				//1) 복귀하면서 앞에 문자 빼고 
				dq.pollFirst();
				//2) 복귀하면서 뒤에 문자 빼고
				dq.pollLast();
				map.put(key, map.get(key)+2);//개수 복귀 
			}
		}
	}
	
	//솔루션 함수 
	public String[] solution(String s){
		//초기화
		dq = new LinkedList<>();
		res = new ArrayList<>();
		map = new HashMap<>();
		len = s.length();
		
		//각 문자 구성별 빈도수 체크
		for(char x : s.toCharArray()) {
			map.put(x, map.getOrDefault(x, 0) +1);
		}
		//1) 애초에 팰린드롬 가능한 구성인지 확인 
		//빈도수 홀수개, 짝수개인지 따라 
		int odd = 0;
		char mid = '#';//임시 초기화 
		
		for(char key : map.keySet()) {
			if(map.get(key) % 2 == 1) { //빈도수 홀수개인지 
				mid = key;//일단 그 키로 세팅
				odd++;//홀수개의 빈도수 문자 개수 카운팅 
			}
		}
		//홀수 빈도 갖는 문자 1개 이상인 경우 어차피 팰린드롬 못 만듬
		if(odd > 1) return new String[] {}; //여기서 빈 문자열 리턴 
		
		if(mid != '#') { //위에서 갱신된 홀수개 문자가 1개 있던지 or 없던지 해서 갱신된 상태면 
			dq.add(mid);//데크 가운데에 1개만 담고 
			map.put(mid, map.get(mid)-1);//빈도수 -1
		}
		//호출
		DFS();
		
		//정답 세팅
		String[] answer = new String[res.size()];
		
		for(int i=0; i<res.size(); i++) { //ArrayList에 담아뒀던 각 String 값 넘겨주기 
			answer[i] = res.get(i);
		}

		return answer;
	}
	//실행 메인 
	public static void main(String[] args){
		Solution T = new Solution();
		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")));
	}
}

---

🟩 5번. 유효한 IP 주소

문제 설명

풀이

• D(i) 의 정의 : 입력 문자열 s에서 i번째 값부터 시작하여 (0~255) 사이의 값을 만들 수 있는 경우의 수로 뻗어나감
• tmp에 각 값에서 갈 수 있는 구분값을 임시로 담아두다가, 그 구분이 4가 되면서 st값이 마지막까지 순회했다면 “.”을 붙여가며 res 리스트에 담아둔다.

package to_0814_3;
//유효한 IP 주소 
import java.util.*;
class Solution {
	static LinkedList<String> tmp;
	static ArrayList<String> res;
	//DFS
	static void DFS(int start, String s) {
		if(tmp.size() == 4 && start == s.length()) {
			String Ts = "";
			for(String x : tmp) Ts += x + ".";
			res.add(Ts.substring(0, Ts.length()-1));//마지막 . 제거하려고 
		}else {
			//입력으로 들어온 start 값을 기준으로 s길이 전까지 순회는 하는데 
			for(int i=start; i<s.length(); i++) {	
				//시작점이 0이면서 i>start인 경우 = 02 이런 식으로 0으로 시작하는 두 자리 이상 숫자로 갈 경우 return
				if(s.charAt(start) == '0' && i > start) return;
				//항상 start부터 뽑고 i는 증가함 
				String num = s.substring(start, i+1);//start지점부터 각 i지점까지 뽑기
				if(Integer.parseInt(num) > 255) return; //그냥 복귀하고 
				tmp.add(num);//자른 문자 담고 
				//마지막으로 뽑은 지점부터 start 지점으로 두고 호출 
				DFS(i+1, s);
				//복귀 - 다른 깊이 탐색 하려면 복귀시키고 
				tmp.pollLast();
			}
		}
	}
	
	//솔루션 함수 
	public String[] solution(String s){
		//초기화
		tmp = new LinkedList<>();//임시 배열 
		res = new ArrayList<>();//. 담은 리스트
		
		DFS(0, s); //문자열 그대로 보내고 
		
		//정답 세팅 
		String[] answer = new String[res.size()];
		for(int i=0; i<res.size(); i++) answer[i] = res.get(i);
		
		return answer;
	}
	//실행 메인 
	public static void main(String[] args){
		Solution T = new Solution();
		System.out.println(Arrays.toString(T.solution("2025505")));	
		System.out.println(Arrays.toString(T.solution("0000")));
		System.out.println(Arrays.toString(T.solution("255003")));
		System.out.println(Arrays.toString(T.solution("155032012")));
		System.out.println(Arrays.toString(T.solution("02325123")));
		System.out.println(Arrays.toString(T.solution("121431211")));
	}
}

---

🟩 6번. 알파코드 | DFS

문제 설명

1차 풀이

DFS(i) 정의 : i번 인덱스부터 시작하여 뻗어갈 수 있는 경우의 수

• DFS의 복귀 기준 :

시작점이 문자열 크기와 같아지면 끝까지 간 것이기 때문에 여기서 answer ++ 처리 후 return 해준다.

• DFS 깊이 탐색 기준

→ i로 st부터 len 전까지 탐색하면서 i인덱스부터 가능한 1~26사이의 값으로만 더 깊이 갈 거다.

따라서 substring처리 한 값이 해당 범위 내의 값일 경우에 한해서 DFS(i+1, s)로 더 깊이 탐색하는 식으로 탐색을 시도헀다.

package to_0816_1;
/*DFS- 알파코드 문제 풀이 */
import java.util.*;
class Solution {
	static int len;
	static int answer;
	
	//dfs
	static void DFS(int st, String s ) {//s는 시작 인덱슽 
		if(st == len) { //DFS(5) 호출 시 복귀 
			answer++;
			return;
		}else {
			for(int i=st; i<len; i++) {
				String num = s.substring(st, i+1);
				if(Integer.parseInt(num) < 1 || Integer.parseInt(num) > 27) return;
				
				DFS(i+1, s);//다음으로 더 깊이
			}
		}
	}
	
	//솔루션 함수 
	public int solution(String s){
		
		len = s.length();
		answer = 0;
		DFS(0, s);

		return answer;
	}
	//실행 메인 
	public static void main(String[] args){
		Solution T = new Solution();
		System.out.println(T.solution("25114"));
		System.out.println(T.solution("23251232"));
		System.out.println(T.solution("21020132"));
		System.out.println(T.solution("21350"));
		System.out.println(T.solution("120225"));
		System.out.println(T.solution("232012521"));
	}
}

---

2차 풀이 | DP + DFS

풀이

• 시간복잡도 줄이기 위해서 반복되는 작업을 메모이제이션으로 담아두고 사용하는 방식

//알파코드 - DP + DFS 풀이 
import java.util.*;
class Solution {
	static int[] dy;
	//DFS
	static int DFS(int st, String s) {
		if(dy[st] > 0) return dy[st];
		if(st < s.length() && s.charAt(st) == '0') return 0;
		if(st ==  s.length() -1 || st == s.length()) return 1;
		else {
			int res = DFS(st+1, s);
			int tmp = Integer.parseInt(s.substring(st, st+2));
			if(tmp <= 26) res += DFS(st+2, s);
			return dy[st] = res;
		}
	}
	//솔루션 함수
	public int solution(String s){
		dy = new int[101];
		int answer = DFS(0, s);

		return answer;
	}
	//실행 메인 
	public static void main(String[] args){
		Solution T = new Solution();
		System.out.println(T.solution("25114"));
		System.out.println(T.solution("23251232"));
		System.out.println(T.solution("21020132"));
		System.out.println(T.solution("21350"));
		System.out.println(T.solution("120225"));
		System.out.println(T.solution("232012521"));
	}
}