[백준 Java] 1759번 - 암호 만들기

1759번 - 암호 만들기 

 

<문제>

 

<예시>

 

문제를 읽고 처음 시도한 접근은 조합입니다. 

6개의 알파벳 문자 중에 4개를 선택하여 암호를 완성한다. 대신 모음은 최소 1개 자음은 최소 2개를 포함한다. 

즉, 6C4(15개)를 구해서 모음이 포함되지 않았거나 자음이 1개 이하로 포함된 암호를 빼줍니다. 

또, 암호는 증가하는 순서로 정렬되었을 것이라고 추측되기 때문에 sort 함수를 사용하여 미리 입력받은 알파벳 문자를 오름차순으로 정렬합니다. 

 

<중요 코드>

* 재귀를 사용하여 조합된 암호를 출력하는 combinatin 함수 

public static void combination(String[] alpha, boolean[] visit, int dep, int r) {
	if(r == 0) {
		print(alpha, visit); //조합된 암호를 출력하는 함수 
		return;
	}
		
	if(dep == C) {
		return;
	}
		
	else {
		visit[dep] = true;
		combination(alpha, visit, dep+1, r-1);
		visit[dep] = false;
		combination(alpha, visit, dep+1, r);
	}
}

 

* 조합에 사용된 모음과 자음의 개수를 체크하는 코드 

for(int i = 0; i < alpha.length; i++) {
	if(visit[i]) {
		if(alpha[i].charAt(0) == 'a' || 
			alpha[i].charAt(0) == 'e' ||
			alpha[i].charAt(0) == 'i' ||
			alpha[i].charAt(0) == 'o' ||
			alpha[i].charAt(0) == 'u') {
			numMo++; //모음 개수
		}
		else {
			numJa++; //자음 개수
		}
	}
}

 

if(visit[i] && numMo >= 1 && numJa >= 2) {
	System.out.print(alpha[i]);
}

이 코드를 구현하는 과정에서 모음의 최소 개수만 체크하고 제출했다가 오답처리가 되어서 한참을 고민했는데 문제를 다시 천천히 읽어보니 당연히 틀린 게 맞더라고요... 자음의 최소 개수 조건을 포함하지 않고 출력했으니...

 

<전체 코드>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.Arrays;

public class Main {
	static String[] alpha;
	static boolean[] visit;
	static int L, C;
	
	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());
		alpha = new String[C];
		
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i < C; i++) {
			alpha[i] = st.nextToken();
		}
		
		Arrays.sort(alpha);
		visit = new boolean[C];
		
		combination(alpha, visit, 0, L);
	}
	
	public static void combination(String[] alpha, boolean[] visit, int dep, int r) {
		if(r == 0) {
			print(alpha, visit);
			return;
		}
		
		if(dep == C) {
			return;
		}
		
		else {
			visit[dep] = true;
			combination(alpha, visit, dep+1, r-1);
			visit[dep] = false;
			combination(alpha, visit, dep+1, r);
		}
	}
	
	public static void print(String[] alpha, boolean[] visit) {
		int numMo = 0; //모음 개수
		int numJa = 0; //자음 개수 
		
		//모음과 자음의 개수 확인 
		for(int i = 0; i < alpha.length; i++) {
			if(visit[i]) {
				if(alpha[i].charAt(0) == 'a' || 
				   alpha[i].charAt(0) == 'e' ||
				   alpha[i].charAt(0) == 'i' ||
				   alpha[i].charAt(0) == 'o' ||
				   alpha[i].charAt(0) == 'u') {
					numMo++;
				}
				else {
					numJa++;
				}
			}
		}
		
		for(int i = 0; i < C; i++) {			
			if(visit[i] && numMo >= 1 && numJa >= 2) {
				System.out.print(alpha[i]);
			}
		}
		
		if(numMo >= 1 && numJa >= 2)
			System.out.println();
	}
}

 

<결과>

콘솔창

 

2022.08.22

 

감사합니다!