https://www.acmicpc.net/problem/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을 출력한다.

제한
1 ≤ 문자열 X, Y, Z의 길이 ≤ 17
1 ≤ k ≤ 문자열 X, Y, Z 길이의 최솟값
문자열 X에는 중복된 문자가 존재하지 않는다.
문자열 Y에는 중복된 문자가 존재하지 않는다.
문자열 Z에는 중복된 문자가 존재하지 않는다.
예제 입력 1

a
a
a
1

예제 출력 1

a

---

풀이

package silver2;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

/*
 * X Y Z 입력
 * 부분문자열 길이 입력
 * XYZ에 대해 부분문자열 조합 생성.
 * 생성된 부분문자열에 대한 빈도를  나타내는 map 생성
 * 그 map에 부분문자열의 빈도 추가
 * 마지막에 map순회하며 빈도가 2 이상인 것 있으면 출력하고 없으면 -1 (flag이용)
 * 출력할 때는 오름차순 정렬하여 해야 함. 
 * */
public class B25328_문자열집합조합하기 {
	static int k;
	static Map<String, Integer>map = new HashMap<String, Integer>();
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		String X = sc.nextLine();
		String Y = sc.nextLine();
		String Z = sc.nextLine();
		k = sc.nextInt();
		
		// X, Y, Z에 대한 부분문자열 생성하고 빈도 검사
		combi(X.toCharArray(), new char[k], 0, 0);
		combi(Y.toCharArray(), new char[k], 0, 0);
		combi(Z.toCharArray(), new char[k], 0, 0);
		
		// map의 String에 대해 오름차순 정렬
		// 정렬하려면 map의 엔트리셋을 전부 넣은 리스트를 만든 후 거기서 엔트리의 key기반으로 정렬해야함
		ArrayList<Map.Entry<String, Integer>> list = new ArrayList<>(map.entrySet());
		list.sort((e1, e2)->e1.getKey().compareTo(e2.getKey()));
		
		// 출력부분
		StringBuilder sb = new StringBuilder();
		boolean flag = false;
		for (Map.Entry<String, Integer> e : list) {
			if(e.getValue() >= 2) { 
				sb.append(e.getKey()).append('\n');
				flag = true;
			}
		}
		if(flag) System.out.print(sb);
		else System.out.println(-1);
	}
	
	// 문자열로부터  부분 문자열들의 개수를 구하는 조합 시작. 부분집합 알고리즘 사용
	// cards[] : 각 문자열의 문자들(조합용 재료)
	// result[] : 조합 완성된 부분문자열. 길이는 k
	// idx는 result를 가리킬 인덱스
	// start는 cards를 가리킬 인덱스
	static void combi(char[] cards, char[] result, int idx, int start) {
		// 기저조건: 부분문자열 생성 완료
		if(idx == k) {
//			System.out.print(Arrays.toString(result)+": ");
			String res = String.valueOf(result); //완성된 부분문자열을 string으로 변경
//			System.out.println(res);
			map.putIfAbsent(res, 0); //처음 나온 부분문자열이면 빈도 1
			map.put(res, map.get(res)+1); //더 나왔을 때 빈도 늘리기
			
			return;
		}
		for (int i = start; i < cards.length; i++) {
			result[idx] = cards[i];
			combi(cards, result, idx+1, i+1);
		}
	}

}

• X Y Z 입력
• 부분문자열 길이 입력
• XYZ에 대해 부분문자열 조합 생성.
• 생성된 부분문자열에 대한 빈도를 나타내는 map 생성
• 그 map에 부분문자열의 빈도 추가
• 마지막에 map순회하며 빈도가 2 이상인 것 있으면 출력하고 없으면 -1 (flag이용)
• 출력할 때는 오름차순 정렬하여 해야 함.

---

결과