[백준 1759] 암호 만들기

[문제 바로가기]👇

1759번: 암호 만들기

 

 

 

 

 

💡풀이💡

문제에서 알 수 있는 정보

C개의 알파벳 중에서 L개의 서로 다른 알파벳 고르기 사전순(오름차순)으로 정렬되어 있음
>> 조합

 

📌 놓쳤던 부분

서로 다른 L개의 알파벳을 고르기 && 암호라서 순서가 다르면 암호가 달라짐
>> 순열!!

이라고 생각해서 순열로 풀었는데 완성된 암호를 보니까 사전순으로 되어 있는 게 아닌 것도 있음

• 사전순으로 정렬 된 것만 암호가 될 수 있기 때문에 한 개의 암호가 완성되면 암호를 구성하는 각 알파벳이 올 수 있는 자리가 고정 됨
  >> 순서가 의미 없음!!

 

1. 입력 받기

모음을 저장하고 있는 ArrayList를 생성

• 완성된 조합이 암호 조건에 맞는지 확인 할 때 모음과 자음을 구분하기 위해!

	static int L,C;
	static char[] pw, input; // pw : 완성된 조합 저장, input : 입력 되는 알파벳
	static List<Character> vowel; // 모음 저장
	static StringBuilder sb;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		sb = new StringBuilder();
		
		L = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		input = new char[C];
		st = new StringTokenizer(br.readLine(), " ");
		for(int i=0; i<C; i++) { // 입력으로 들어온 알파벳 저장
			input[i] = st.nextToken().charAt(0);
		}
		vowel = new ArrayList<>(Arrays.asList('a','e','i','o','u')); // 모음 저장
		
		// 조합
	}

 

2. 조합

C개 중에서 L개의 알파벳을 골라서 조합하기

조합이 완성되었을 때 완성된 조합이 암호의 규칙에 맞는지 확인(isValidate() )

• 암호의 규칙에 맞다면 StringBuilder에 추가하기

static void comb(int cnt, int start) {
	if(cnt == L) {
		//조합 완성
		if(isValidate()) { // 암호 규칙에 맞으면 추가
			for(char c : pw) sb.append(c);
			sb.append("\\n");
		}
		return;
	}
		
	for(int i=start; i<C; i++) {
		pw[cnt] = input[i];
		comb(cnt+1, i+1);
	}
}

 

암호 규칙에 맞는지 확인

완성된 조합을 순회하면서 모음이면 모음 개수 증가, 자음이면 자음 개수 증가

 

암호 조건

모음 : 1개 이상
자음 : 2개 이상

순회가 끝나면 모음과 자음의 개수가 암호의 조건을 만족하면 true 아니면 false를 리턴

static boolean isValidate() {
	int vowelCnt=0, consCnt=0; // vowelCnt : 모음 개수, consCnt : 자음 개수
		
	for(int i=0; i<L; i++) { // 완성된 암호 순회
		if(vowel.contains(pw[i])) vowelCnt++; // 모음이면
		else consCnt++;			     // 자음이면
	}
	return (vowelCnt>=1 && consCnt>=2) ? true : false;
}

 

전체 코드

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

public class Main {
	static int L,C;
	static char[] pw, input;
	static List<Character> vowel;
	static StringBuilder sb;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		sb = new StringBuilder();
		
		L = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		input = new char[C];
		st = new StringTokenizer(br.readLine(), " ");
		for(int i=0; i<C; i++) {
			input[i] = st.nextToken().charAt(0);
		}
		
		Arrays.sort(input);
		pw = new char[L];
		vowel = new ArrayList<>(Arrays.asList('a','e','i','o','u'));
		comb(0, 0);
		System.out.println(sb.toString());
	}
	
	static void comb(int cnt, int start) {
		if(cnt == L) {
			//조합 완성
			if(isValidate()) {
				for(char c : pw) sb.append(c);
				sb.append("\\n");
			}
			return;
		}
		
		for(int i=start; i<C; i++) {
			pw[cnt] = input[i];
			comb(cnt+1, i+1);
		}
	}

	static boolean isValidate() {
		int vowelCnt=0, consCnt=0;
		
		for(int i=0; i<L; i++) {
			if(vowel.contains(pw[i])) vowelCnt++;
			else consCnt++;
		}
		return (vowelCnt>=1 && consCnt>=2) ? true : false;
	}
}