[Algorithm] ๐Ÿ”๋ฐฑ์ค€ 1759 ์•”ํ˜ธ๋งŒ๋“ค๊ธฐ

0. ๋ฌธ์ œ

๋ฐ”๋กœ ์–ด์ œ ์ตœ๋ฐฑ์ค€ ์กฐ๊ต๊ฐ€ ๋ฐฉ ์—ด์‡ ๋ฅผ ์ฃผ๋จธ๋‹ˆ์— ๋„ฃ์€ ์ฑ„ ๊นœ๋นกํ•˜๊ณ  ์„œ์šธ๋กœ ๊ฐ€ ๋ฒ„๋ฆฌ๋Š” ํ™ฉ๋‹นํ•œ ์ƒํ™ฉ์— ์ง๋ฉดํ•œ ์กฐ๊ต๋“ค์€, 702ํ˜ธ์— ์ƒˆ๋กœ์šด ๋ณด์•ˆ ์‹œ์Šคํ…œ์„ ์„ค์น˜ํ•˜๊ธฐ๋กœ ํ•˜์˜€๋‹ค. ์ด ๋ณด์•ˆ ์‹œ์Šคํ…œ์€ ์—ด์‡ ๊ฐ€ ์•„๋‹Œ ์•”ํ˜ธ๋กœ ๋™์ž‘ํ•˜๊ฒŒ ๋˜์–ด ์žˆ๋Š” ์‹œ์Šคํ…œ์ด๋‹ค.
์•”ํ˜ธ๋Š” ์„œ๋กœ ๋‹ค๋ฅธ L๊ฐœ์˜ ์•ŒํŒŒ๋ฒณ ์†Œ๋ฌธ์ž๋“ค๋กœ ๊ตฌ์„ฑ๋˜๋ฉฐ ์ตœ์†Œ ํ•œ ๊ฐœ์˜ ๋ชจ์Œ(a, e, i, o, u)๊ณผ ์ตœ์†Œ ๋‘ ๊ฐœ์˜ ์ž์Œ์œผ๋กœ ๊ตฌ์„ฑ๋˜์–ด ์žˆ๋‹ค๊ณ  ์•Œ๋ ค์ ธ ์žˆ๋‹ค. ๋˜ํ•œ ์ •๋ ฌ๋œ ๋ฌธ์ž์—ด์„ ์„ ํ˜ธํ•˜๋Š” ์กฐ๊ต๋“ค์˜ ์„ฑํ–ฅ์œผ๋กœ ๋ฏธ๋ฃจ์–ด ๋ณด์•„ ์•”ํ˜ธ๋ฅผ ์ด๋ฃจ๋Š” ์•ŒํŒŒ๋ฒณ์ด ์•”ํ˜ธ์—์„œ ์ฆ๊ฐ€ํ•˜๋Š” ์ˆœ์„œ๋กœ ๋ฐฐ์—ด๋˜์—ˆ์„ ๊ฒƒ์ด๋ผ๊ณ  ์ถ”์ธก๋œ๋‹ค. ์ฆ‰, abc๋Š” ๊ฐ€๋Šฅ์„ฑ์ด ์žˆ๋Š” ์•”ํ˜ธ์ด์ง€๋งŒ bac๋Š” ๊ทธ๋ ‡์ง€ ์•Š๋‹ค.
์ƒˆ ๋ณด์•ˆ ์‹œ์Šคํ…œ์—์„œ ์กฐ๊ต๋“ค์ด ์•”ํ˜ธ๋กœ ์‚ฌ์šฉํ–ˆ์„ ๋ฒ•ํ•œ ๋ฌธ์ž์˜ ์ข…๋ฅ˜๋Š” C๊ฐ€์ง€๊ฐ€ ์žˆ๋‹ค๊ณ  ํ•œ๋‹ค. ์ด ์•ŒํŒŒ๋ฒณ์„ ์ž…์ˆ˜ํ•œ ๋ฏผ์‹, ์˜์‹ ํ˜•์ œ๋Š” ์กฐ๊ต๋“ค์˜ ๋ฐฉ์— ์นจํˆฌํ•˜๊ธฐ ์œ„ํ•ด ์•”ํ˜ธ๋ฅผ ์ถ”์ธกํ•ด ๋ณด๋ ค๊ณ  ํ•œ๋‹ค. C๊ฐœ์˜ ๋ฌธ์ž๋“ค์ด ๋ชจ๋‘ ์ฃผ์–ด์กŒ์„ ๋•Œ, ๊ฐ€๋Šฅ์„ฑ ์žˆ๋Š” ์•”ํ˜ธ๋“ค์„ ๋ชจ๋‘ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค.

์ž…๋ ฅ
์ฒซ์งธ ์ค„์— ๋‘ ์ •์ˆ˜ L, C๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. (3 โ‰ค L โ‰ค C โ‰ค 15) ๋‹ค์Œ ์ค„์—๋Š” C๊ฐœ์˜ ๋ฌธ์ž๋“ค์ด ๊ณต๋ฐฑ์œผ๋กœ ๊ตฌ๋ถ„๋˜์–ด ์ฃผ์–ด์ง„๋‹ค. ์ฃผ์–ด์ง€๋Š” ๋ฌธ์ž๋“ค์€ ์•ŒํŒŒ๋ฒณ ์†Œ๋ฌธ์ž์ด๋ฉฐ, ์ค‘๋ณต๋˜๋Š” ๊ฒƒ์€ ์—†๋‹ค.

์ถœ๋ ฅ
๊ฐ ์ค„์— ํ•˜๋‚˜์”ฉ, ์‚ฌ์ „์‹์œผ๋กœ ๊ฐ€๋Šฅ์„ฑ ์žˆ๋Š” ์•”ํ˜ธ๋ฅผ ๋ชจ๋‘ ์ถœ๋ ฅํ•œ๋‹ค.

1. ๋ฌธ์ œ ๊ฐ„๋‹จ ํ•ด์„

C๊ฐœ์˜ ์„œ๋กœ ๋‹ค๋ฅธ ์•ŒํŒŒ๋ฒณ์œผ๋กœ L์ž๋ฆฌ์˜ ์•”ํ˜ธ๋ฅผ ๋งŒ๋“ค์–ด์•ผํ•จ

์•”ํ˜ธ๋Š” ์ž์Œ 2๊ฐœ ์ด์ƒ, ๋ชจ์Œ 1๊ฐœ์ด์ƒ์ด์–ด์•ผ ํ•˜๊ณ 

์•ŒํŒŒ๋ฒณ์ด ์˜ค๋ฆ„์ฐจ์ˆœ์œผ๋กœ ์ •๋ ฌ๋˜์–ด ์žˆ์–ด์•ผํ•จ

2. ์•„์ด๋””์–ด

๐Ÿ’ก ์ž์Œ 2๊ฐœ ์ด์ƒ, ๋ชจ์Œ 1๊ฐœ ์ด์ƒ์„ ์ฒดํฌํ•˜๋Š” ํ•จ์ˆ˜
๐Ÿ’ก ์•ŒํŒŒ๋ฒณ์„ ๋ฐฐ์—ด์— ๋„ฃ๊ณ  ์˜ค๋ฆ„์ฐจ์ˆœ์œผ๋กœ ์ •๋ ฌ
๐Ÿ’ก ์žฌ๊ท€ํ•จ์ˆ˜๋ฅผ ์ด์šฉํ•˜์—ฌ ๋ชจ๋“  ๊ฒฝ์šฐ๋ฅผ ํƒ์ƒ‰

3. ํ•ต์‹ฌ ํ’€์ด

1) ์ž์Œ 2๊ฐœ ์ด์ƒ, ๋ชจ์Œ 1๊ฐœ ์ด์ƒ์„ ์ฒดํฌํ•˜๋Š” ํ•จ์ˆ˜

if(cons >=2 && vowel >=1)
	return true;
else
	return false;

2) ์•ŒํŒŒ๋ฒณ์„ ๋ฐฐ์—ด์— ๋„ฃ๊ณ  ์˜ค๋ฆ„์ฐจ์ˆœ์œผ๋กœ ์ •๋ ฌ

Arrays.sort(alpha);

3) ์žฌ๊ท€ํ•จ์ˆ˜๋ฅผ ์ด์šฉํ•˜์—ฌ ๋ชจ๋“  ๊ฒฝ์šฐ๋ฅผ ํƒ์ƒ‰

dfs(pwd+alpha[i],i+1);
dfs(pwd,i+1);

4. ์ฝ”๋“œ

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

public class BOJ_1759 {
	static int L, C, result[];
	static char alpha[];
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String s[] = br.readLine().split(" ");
		
		L = Integer.parseInt(s[0]);
		C = Integer.parseInt(s[1]);
		
		alpha = new char[C];
		result = new int[C];
		
		s = br.readLine().split(" ");
		
		for(int i=0; i<C; i++)
			alpha[i] = s[i].charAt(0);
		
		Arrays.sort(alpha);
		
		dfs("",0);
			
	}
	
	public static void dfs(String pwd, int i) {
		if(pwd.length() == L && check(pwd)) {
			System.out.println(pwd);
			return;
		}
		if(alpha.length <= i)
			return;
		
		dfs(pwd+alpha[i],i+1);
		dfs(pwd,i+1);
		
	}

	public static boolean check(String pwd) {
		int cons = 0;
		int vowel = 0;
		
		for(char c : pwd.toCharArray()) {
			if(c == 'a' || c == 'e' || c =='i' || c =='o' || c=='u')
				vowel++;
			else
				cons++;
		}
		
		if(cons >=2 && vowel >=1)
			return true;
		else
			return false;
	}
}

5. ๊ฒฐ๊ณผ

์„ฑ๊ณต~

์ข‹์€ ์›นํŽ˜์ด์ง€ ์ฆ๊ฒจ์ฐพ๊ธฐ