BOJ 1759 암호 만들기 [Java]
문제
접근방법
- 보통 사용자의 입력에 따라 길이가 정해지는 문제는 재귀를 활용하는 경우가 많음
- 그래서 DFS로 접근
- 사전식이라고 언급되었기 때문에 정렬을 먼저 생각
- 모든 경우의 수를 방문해야 할 것 같기는 하지만, 사전식이라는 점에서 중간중간 탈출을 꾀할 수 있을 것 같음
구현
import java.io.*;
import java.util.*;
/*
input
4 6
a t c i s w
*/
class Main {
static int L, C;
static char[] letters;
static char[] result;
public static void main(String [] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ", false);
L = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
result = new char[C];
letters = new char[C];
st = new StringTokenizer(br.readLine(), " ", false);
for (int i = 0; i < C; i++) {
letters[i] = st.nextToken().charAt(0);
}
Arrays.sort(letters);
DFS(0,0,0,0);
}
static void BFS(int start, int depth, int ja, int mo) {
for (int i = start; i < C; i++) {
result[i] = 1;
int j = ja;
int m = mo;
if(letters[i] == 'a' || letters[i] == 'e' || letters[i] == 'i'|| letters[i] == 'o' || letters[i] == 'u') m++;
else j++;
DFS(i+1,depth+1,j,m);
result[i] = 0;
}
if(depth == L && ja >= 2 && mo >= 1) {
for (int k = 0; k < C; k++) {
if (result[k] == 1) System.out.print(letters[k] + "");
}
System.out.println();
}
}
}
제출
Author And Source
이 문제에 관하여(BOJ 1759 암호 만들기 [Java]), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@sheltonwon/BOJ-1759-JAVA저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)