백준 17255 - N으로 만들기

[문제 바로가기]

 

1. 유형

DFS

 

2. 문제 분석

2-1. 설계

시작 위치를 탐색 -> 함수 시작 -> 현 위치에서 왼쪽, 오른쪽으로 재귀 진행 -> 총 N-1개를 탐색하면 종료

 

2-2. 설명

투포인터를 사용했습니다.

[그림1]은 "521"중 2를 시작위치로 설정했을 때의 경우 입니다. 왼쪽, 오른쪽에 포인터를 두고 path변수에 만든 루트를 저장합니다. 그리고 Set 컬렉션에서 중복을 제외해주면 됩니다.

그림1

 

 

3. 코드

import java.io.*;
import java.util.*;

public class Main {
	static char[] arr;
	static Set<String> set;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		arr = st.nextToken().toCharArray();
		set = new HashSet<>();
		for(int i=0; i<arr.length; i++) {
			dfs(i,i, ""+arr[i], ""+arr[i]);
		}
		System.out.println(set.size());
	}
	static void dfs(int L, int R, String s, String path) {
		if(L==0 && R==arr.length-1) {
			set.add(path);
			return;
		}
		if(L-1>=0) {
			dfs(L-1, R, arr[L-1]+s, path+" "+arr[L-1]+s);
		}
		if(R+1<arr.length) {
			dfs(L, R+1, s+arr[R+1], path+" "+s+arr[R+1]);
		}
	}
	static int stoi(String s) {
		return Integer.valueOf(s);
	}
}