[백준(Baekjoon)] 1759. 암호 만들기

 

 

[백준(Baekjoon)] 1759. 암호 만들기

 

 

1759번: 암호 만들기

 

 

[입력]

 

첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다.

 

 

[출력]

 

각 줄에 하나씩, 사전식으로 가능성 있는 암호를 모두 출력한다.

 

 

[풀이]

 

우선 C개의 문자열에서 L개의 문자를 택하여 암호를 만드는 방식이라 순열을 사용했다.

순열 사용하여 암호를 만들면서 암호길이가 2이상일 경우 앞문자와 비교하여 알파벳순(오름차순)인지 확인한다.

알파벳순이 아닐 경우 암호 만드는 것을 멈추고 그 다음 반복문을 실행한다.

이렇게 알파벳순으로 만든 암호가 가능한지 체크해주는 함수를 만들어 true를 반환한 경우만 list에 추가해준다.

이 list는 암호 알파벳순으로 나열되어있지 않아 sort해준 후 출력한다.

 

 

[코드]

 

public class al1759 {

	static int L,C;
	static char[] s;
	static char[] ns;
	static boolean[] isUsed;
	static ArrayList<String> list = new ArrayList<>();
	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());
		isUsed = new boolean[26];
		
		st = new StringTokenizer(br.readLine());
		s = new char[C];
		ns = new char[L];
		for (int i = 0; i < C; i++) {
			s[i] = st.nextToken().charAt(0);
		}
		
		perm(0);
		
		Collections.sort(list);
		for (String pw : list) {
			System.out.println(pw);
		}

	}
	
	private static void perm(int cnt) {
		if(cnt == L) {
			if(!poss(ns)) return; //암호 조건 불만족시 리턴
            //조건 만족하는 것만 list에 저장
			StringBuilder sb = new StringBuilder();
			for (char n : ns) {
				sb.append(n);
			}
			list.add(sb.toString());
			return;
		}
		
		for (int i = 0; i < C; i++) {
			if(isUsed[s[i] - 'a']) continue; //소문자 알파벳 사용여부 체크
			
			if(cnt > 0) { //암호는 알파벳순으로 생성 되어야함
				if(ns[cnt-1] - 'a' > s[i] - 'a') continue;
			}
			
            //순열생성
			isUsed[s[i] - 'a'] = true;
			ns[cnt] = s[i];
			perm(cnt+1);
			isUsed[s[i] - 'a'] = false;
		}
	}
	
	private static boolean poss(char[] str) { //암호 가능 여부
		int vowel = 0;
		int consonant = 0;
		for (int i = 0; i < str.length; i++) {
			char ch = str[i];
			if(ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u') {
				vowel++; //모음 세기
			}else {
				consonant++; //자음 세기
			}
		}
		
        //모음이 최소 한개 이상이고 자음이 최소 두개 이상인지 확인
		if(vowel >= 1 && consonant >= 2) return true;
		
		return false;
	}

}