[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. ๊ฒฐ๊ณผ
์ฑ๊ณต~
Author And Source
์ด ๋ฌธ์ ์ ๊ดํ์ฌ([Algorithm] ๐๋ฐฑ์ค 1759 ์ํธ๋ง๋ค๊ธฐ), ์ฐ๋ฆฌ๋ ์ด๊ณณ์์ ๋ ๋ง์ ์๋ฃ๋ฅผ ๋ฐ๊ฒฌํ๊ณ ๋งํฌ๋ฅผ ํด๋ฆญํ์ฌ ๋ณด์๋ค https://velog.io/@kha0318/Algorithm-๋ฐฑ์ค-1759-์ํธ๋ง๋ค๊ธฐ์ ์ ๊ท์: ์์์ ์ ๋ณด๊ฐ ์์์ URL์ ํฌํจ๋์ด ์์ผ๋ฉฐ ์ ์๊ถ์ ์์์ ์์ ์ ๋๋ค.
์ฐ์ํ ๊ฐ๋ฐ์ ์ฝํ ์ธ ๋ฐ๊ฒฌ์ ์ ๋ (Collection and Share based on the CC Protocol.)
์ข์ ์นํ์ด์ง ์ฆ๊ฒจ์ฐพ๊ธฐ
๊ฐ๋ฐ์ ์ฐ์ ์ฌ์ดํธ ์์ง
๊ฐ๋ฐ์๊ฐ ์์์ผ ํ ํ์ ์ฌ์ดํธ 100์ ์ถ์ฒ ์ฐ๋ฆฌ๋ ๋น์ ์ ์ํด 100๊ฐ์ ์์ฃผ ์ฌ์ฉํ๋ ๊ฐ๋ฐ์ ํ์ต ์ฌ์ดํธ๋ฅผ ์ ๋ฆฌํ์ต๋๋ค