[백준/자바] 1759번: 암호 만들기

문제

https://www.acmicpc.net/problem/1759

풀이

• 암호는 서로 다른 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()); // 주어진 알파벳의 수
		
		arr = new String[c]; // 알파벳 종류를 저장할 배열
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < c; i++) {
			arr[i] = st.nextToken();
		}
		
		Arrays.sort(arr); // 정렬
		
		result = new String[l]; // 암호 후보를 저장할 배열

• 문제에서 암호는 알파벳이 오름차순으로 이루어져 있다고 하므로 문자열 정렬이 필수입니다!

조합 추출

	private static void dfs(int depth, int start) {
		if (depth == l) { // 기저 조건
			if (isValid()) { // 암호 조건에 만족하는지 검사
				for (String s : result) { // 만족한다면 StringBuilder에 추가
					sb.append(s);
				}
				sb.append('\n');
			}
			return;
		}
		
        // 가능한 모든 조합 뽑기
		for (int i = start; i < c; i++) {
			result[depth] = arr[i];
			dfs(depth + 1, i + 1);
		}
	}

• 조합 코드가 이해가 가지 않는 분은 여기를 클릭하셔서 조합의 기초 문제부터 풀고 오시는 것을 추천드립니다!

유효성 검사

	static final String vow = "aeiou"; // 모음
    
	private static boolean isValid() {
		int cnt = 0; // 모음의 개수
		for (String s : result) {
			if (vow.contains(s)) { // 모음이 발견되면 cnt 증가
				cnt++;
			}
		}
		
        // 모음은 최소 1개, 자음은 최소 2개가 필요함
		if (cnt == 0 || l - cnt < 2) return false;
		
		return true;
	}

• 문제 조건을 잘 읽으셨으면, 쉽게 풀 수 있습니다.

출력

		dfs(0, 0);
		
		System.out.println(sb.toString());

• StringBuilder에 저장한 값들을 모두 출력하면 끝!

코드

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

public class Main {
	static StringBuilder sb = new StringBuilder();
	static int l, c;
	static String[] arr, result;
	static boolean[] visited;
	
	static final String vow = "aeiou";
	
	private static void dfs(int depth, int start) {
		if (depth == l) {
			if (isValid()) {
				for (String s : result) {
					sb.append(s);
				}
				sb.append('\n');
			}
			return;
		}
		
		for (int i = start; i < c; i++) {
			result[depth] = arr[i];
			dfs(depth + 1, i + 1);
		}
	}
	
	private static boolean isValid() {
		int cnt = 0;
		for (String s : result) {
			if (vow.contains(s)) {
				cnt++;
			}
		}
		
		if (cnt == 0 || l - cnt < 2) return false;
		
		return true;
	}
	
	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());
		
		arr = new String[c];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < c; i++) {
			arr[i] = st.nextToken();
		}
		
		Arrays.sort(arr);
		
		result = new String[l];
		dfs(0, 0);
		
		System.out.println(sb.toString());
	}
}