Baekjoon 25328 문자열 집합 조합하기 JAVA

25328번: 문자열 집합 조합하기

문제

알파벳 소문자로 구성된 문자열 X, Y, Z가 주어진다. 각각의 문자열에는 중복된 문자가 존재하지 않는다. 문자열 S에 있는 문자 중 임의로 k개를 선택하여 문자열 S에서의 순서를 유지하여 만든 모든 부분 문자열을 모아 놓은 집합을 문자열 S에 대한 조합 C(S, k)라고 하자. 예를 들어, 문자열 S = 'abc'에 대한 조합 C(S, 2) = {'ab', 'ac', 'bc'}이다. 입력으로 문자열 X, Y, Z와 정수 k가 주어질 때 C(X, k), C(Y, k), C(Z, k)에 두 번 이상 나타나는 부분 문자열을 오름차순으로 출력하자.

입력

첫 번째 줄에 문자열 X가 주어진다.

두 번째 줄에 문자열 Y가 주어진다.

세 번째 줄에 문자열 Z가 주어진다.

네 번째 줄에 정수 k가 주어진다.

출력

C(X, k), C(Y, k), C(Z, k)에 두 번 이상 나타나는 부분 문자열을 오름차순으로 출력한다. 한 줄에 하나의 부분 문자열을 출력한다. 두 번 이상 나타나는 부분 문자열이 없으면 -1을 출력한다.

풀이

각 입력되는 문자열을 이용하여 만들 수 있는 모든 문자열을 백트래킹을 이용하여 생성을 한다.

생성을 할때 hs HashSet에 저장을 하고 이미 hs에 존재하는 값이라면 dup HashSet에 저장을 해준다.

생성 후 Iterator를 이용하여 값을 정렬하고 출력을 한다

코드

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

public class Main {
	static HashSet<String> hs = new HashSet<String>(), dup=new HashSet<String>();
	static int k;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String [] x=new String[3];
		int i=0;
		for(i=0;i<3;i++)
			x[i]=br.readLine();
		k=Integer.parseInt(br.readLine());
		for(i=0;i<3;i++)
			make(x[i],new char[k],0,0);	// char의 최대 길이는 k와 동일하기에 k사이즈릐 char 배열을 할당
		if(dup.size()==0)	// 중복되는 문자열이 없으면 -1을 출력
			bw.write("-1");
		else {
			Iterator<String> iter = dup.iterator();	// dup Set의 내용들을 Iterator를 이용하여 출력
			String [] ans = new String [dup.size()];	// ans를 dup size만큼 할당후 
			i=0;
			while(iter.hasNext())	// 모든 내용들을 ans에 전달
				ans[i++]=iter.next();
			Arrays.sort(ans);	// 오름차순으로 출력하기 위한 정렬을 함
			for(i=0;i<dup.size();i++)	// 답안 출력
				bw.write(ans[i]+"\n");
		}
		bw.close();
	}
	
	public static void make(String str,char [] nstr, int s, int depth) {
		if(depth==k) {	// k 길이만큼의 문자열이 생성되었다면 
			if(hs.contains(String.valueOf(nstr)))	// 이미 출현한 hs Set안에 있다면 duplication Set에 추가한다
				dup.add(String.valueOf(nstr));
			else	// 처음 등장하는 배열이라면 hs set에 저장
				hs.add(String.valueOf(nstr));
			return;
		}
		for(int i=s;i<str.length();i++) {	// 순열을 이용하여 모든 경우의 수가 가능한 문자열을 생성한다
			nstr[depth]=str.charAt(i);
			make(str,nstr,i+1, depth+1);
		}
	}
}