[백준 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을 출력한다.

---

Main.java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class Main{
	static int K;
	static char[] selected;
	static Map<String, Integer> map;
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		String X = bf.readLine(); // 문자열 입력
		String Y = bf.readLine();
		String Z = bf.readLine();

		K = Integer.parseInt(bf.readLine()); // 만들 문자열 개수
		selected = new char[K]; // 만들어진 조합
		
		map = new HashMap<>(); // 나 이거 처음 써봐 ..아닌가
		PriorityQueue<String> ans = new PriorityQueue<>(); // 오름차순 출력을 위해 사용
		
		// 각 문자열로 조합 만들기
		comb(0, 0, X);
		comb(0, 0, Y);
		comb(0, 0, Z);
		
		for (String key: map.keySet()) {
			int tmp = map.get(key); // 해당 문자열의 횟수가
			if(tmp>=2) { // 2 이상이면 우선순위 큐에 저장
				ans.offer(key);
			}
		}
		
		if(ans.isEmpty()) { // 저장된 문자열이 없다면
			System.out.println(-1);
		}else {
			while(!ans.isEmpty()) { // 문자열이 존재하면 큐가 빌때까지 출력
				System.out.println(ans.poll());
			}
		}
		
	} // main end
	private static void comb(int cnt, int start, String s) {
		if(cnt==K) { // 만들 조합의 수만큼 골랐으면 문자열을 만들기
			String pick = String.valueOf(selected);
			map.merge(pick, 1, Integer::sum); // 문자열과 기존 횟수+1 .. 윤환님 땡큐 ..
			return;
		}

		for(int i=start;i<s.length();i++) {
			selected[cnt] = s.charAt(i); // 고르고
			comb(cnt+1, i+1, s); // 다음 자리
		}
	}
}

---

출처

https://www.acmicpc.net/problem/25328

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