728x90
반응형
문제
https://www.acmicpc.net/problem/1759
풀이 방법
골드 문제 치고는 간단한 듯 싶었다. 더 효율적인 방법이 있겠지만 나는 제일 먼저 떠오르는 방법으로 구현했다.
1. 주어진 문자들 중에서 L개를 뽑는 조합을 먼저 구하고
2. 완성된 조합을 가능성이 있는지 판단하는 순서로 구현했다.
제출 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class BJ_1759_암호만들기 {
public static int L, C;
public static char[]inputs;
public static char[] pwd;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
L = Integer.parseInt(st.nextToken()); //만들어야하는 암호의 자릿수
C = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
inputs = new char[C]; //입력받은 알파벳을 저장
pwd = new char[L];
for (int i = 0; i < C; i++) {
inputs[i] = st.nextToken().charAt(0);
}
Arrays.sort(inputs); //순서대로 만들어야하기 때문에 미리 정렬하기
combination(0, 0); //조합 시작
}
private static void combination(int cnt, int start) {
if(cnt ==L) {
if(check(pwd)) { //조합이 완성되면 가능성있는지 확인
for (char c : pwd) { //가능성있으면 출력
System.out.print(c);
}
System.out.println();
};
return;
}
for (int i = start; i < C; i++) {
pwd[cnt] = inputs[i];
combination(cnt+1, i+1);
}
}
private static boolean check(char[] pwd) {
int j =0; //자음 개수
int m =0; //모음 개수
for (int i = 0; i < pwd.length; i++) {
//모음이면 m에 추가 자음이면 j변수에 추가
if( pwd[i] =='a' ||pwd[i] =='e'||pwd[i] =='i'||pwd[i] =='o'||pwd[i] =='u') m++;
else j++;
}
if(j >=2 && m>=1) return true; //모음이 1개이상 자음 2개 이상이면 true
else return false; //아니면 false
}
}
728x90
반응형
'알고리즘 > BJ' 카테고리의 다른 글
[BJ] 백준 10026 적록색약 (JAVA) (0) | 2022.02.23 |
---|---|
[BJ] 백준 2669 직사각형 네 개의 합집합의 면적구하기 (JAVA) (0) | 2022.02.22 |
[BJ] 백준 1260 DFS와 BFS (JAVA) (0) | 2022.02.21 |
[BJ] 백준 2477 참외밭 (JAVA) (0) | 2022.02.21 |
[BJ] 10157 자리배정 (JAVA) (0) | 2022.02.19 |