[BOJ 백준] 암호만들기(1759) Java

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

1759번: 암호 만들기

 

문제 설명 : 

바로 어제 최백준 조교가 방 열쇠를 주머니에 넣은 채 깜빡하고 서울로 가 버리는 황당한 상황에 직면한 조교들은, 702호에 새로운 보안 시스템을 설치하기로 하였다. 이 보안 시스템은 열쇠가 아닌 암호로 동작하게 되어 있는 시스템이다.

암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다. 또한 정렬된 문자열을 선호하는 조교들의 성향으로 미루어 보아 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되었을 것이라고 추측된다. 즉, abc는 가능성이 있는 암호이지만 bac는 그렇지 않다.

새 보안 시스템에서 조교들이 암호로 사용했을 법한 문자의 종류는 C가지가 있다고 한다. 이 알파벳을 입수한 민식, 영식 형제는 조교들의 방에 침투하기 위해 암호를 추측해 보려고 한다. C개의 문자들이 모두 주어졌을 때, 가능성 있는 암호들을 모두 구하는 프로그램을 작성하시오.

 

입력 : 

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

 

출력 : 

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

 

예제 입력 : 

4 6
a t c i s w

 

예제 출력 : 

acis
acit
aciw
acst
acsw
actw
aist
aisw
aitw
astw
cist
cisw
citw
istw

 

접근법 : 

1) 어떻게 풀 것인가?

암호를 풀어야하는데 길이는 최대 15이고 ① 알파벳은 무조건 1개씩만 사용하며, ② 오름차순으로 암호를 사용한다.

③ 모음 1개 이상, 자음 2개 이상을 반드시 사용해야한다.

 

위의 조건들을 잘 보면

① 알파벳은 무조건 1개씩만 사용 → 제곱의 경우가 아닌 순열으로 경우의 수를 낮춰줌

② 오름차순으로 암호를 사용한다. → 순열이 아닌 조합으로 경우의 수를 낮춰줌 (순서가 전혀 상관없으므로)

 

여기까지만 해도 조합으로 문제 해결이 가능하다. 즉, 단순 DFS 또는 백트래킹으로 문제를 풀 경우 가능하다.

15길이의 조합의 최대 값은 15C7의 6,435 가지 경우의 수이므로 넉넉하다.

 

여기에 조건을 조금 더 활용한다면,

③ 모음 1개 이상, 자음 2개 이상을 반드시 사용해야한다.

→ 모음 없이 자음만 있는 경우 답이 아님

    Ex> a c e d i j k l p q s t v w x 라는 경우가 주어지고 암호 길이가 7일때

      ③ 조건으로 인해 a, i 가 모두 제외된 경우는 확인하지 않아도 된다. 즉, 13Combination7 의 경우의 수가 절약된다.

      즉, 전체 15Combination7 = 6,435 가지 경우의 수 중 1,716 경우의 수를 절약 가능 (약 27% 절감)

 

참고 : 무차별 대입 공격 (브루트포스)

https://ko.wikipedia.org/wiki/%EB%AC%B4%EC%B0%A8%EB%B3%84_%EB%8C%80%EC%9E%85_%EA%B3%B5%EA%B2%A9

무차별 대입 공격 - 위키백과, 우리 모두의 백과사전

 

2) 시간복잡도

앞서 분석을 했는데 최악의 경우도 6,435가지이므로 C나 C++의 경우엔 왠만하면 0ms가 가능할듯.

(Java 기준 -  108ms)

 

3) 공간복잡도

위의 경우의 수를 계산해서 넉넉하게 10,000개의 정답 String 배열을 선언해줘도 될듯하고 

사실 정답 배열은 필요없이 순서대로 바로 출력해도 무방하다.

굳이 계산을 해보자면 10,000 개에 최대 15개의 char라면

150,000 * 1Bytes = 146Kbytes 로 아주 작다.

그래도 Java를 쓴다면 ArrayList로 동적배열을 하는  것이 난이도가 올라가면 활용도가 더 많으므로 추천.

 

4) 풀면서 놓쳤던점

특별히 없음. DFS 중에서 난이도 쉬운 편

 

5) 이 문제를 통해 얻어갈 것

DFS, 백트래킹 기본 구현.

조건이 추가될때 어떻게 구현할 것인지 (모음, 자음 제한조건)

백준 1062 가르침 문제랑 같이 풀기 좋다.

문제 : https://www.acmicpc.net/problem/1062 

1062번: 가르침

풀이 : https://subbak2.tistory.com/5

[BOJ 백준] 가르침(1062) Java

 

Java 코드 : 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

// 암호만들기 백준 1759
public class Main {

	static int L, C;				// L은 길이, C는 알파벳 개수
	static int lastMoeum;			// 마지막 모음이 있는 곳을 기록 (dfs 가지치기를 위함)
	
	static String[] input;			// input 받은 배열
	static ArrayList<String> answer;			// 답 순서를 저장할 배열
	
	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(br.readLine());
		
		// L 비밀번호길이 / C 문자개수
		L = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());

		// input 배열에 가능한 알파벳 입력받기
		input = new String[C];
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<C; i++)
		{
			input[i] = st.nextToken();
		}
		// input 오름차순으로 정렬
		Arrays.sort(input);
		
		// 마지막 모음을 체크 -> dfs에서 가지치기를 위함
		lastMoeum = 0;
		for (int i=1; i<C; i++) {
			String tmp = input[i];
			if (tmp.equals("e")||tmp.equals("i")||tmp.equals("o")||tmp.equals("u")) {
				lastMoeum = i;
			}
		}
		
		// 답은 동적배열로 가능하게 선언
		answer = new ArrayList<String>();
		dfs(0, 0, 0, "");	// id : 현재위치/ moeum : 모음 Cnt / cnt : 만든 배열 길이 / ans : 정답String
		
		// 정답 출력
		int size = answer.size();
		for (int i = 0; i<size; i++) {
			bw.write(answer.get(i)+"\n");
		}
			
		bw.flush();
		bw.close();
		br.close();
	}
	
	
	static void dfs(int id, int moeum, int cnt, String ans) {		// id : 현재위치	/	 moeum : 모음 개수 	/	cnt : 만든 배열 길이
		// 글자 개수를 다 채우고 모음이 1개면 정답에 추가 
		if (cnt == L && moeum>=1 && cnt-moeum>=2) {
			answer.add(ans);
			return;
		}
		if (id == C) return;	// 배열 못 채우고 끝
		if (moeum==0 && id>lastMoeum) return;	// 모음을 충족할 수 없어서 끝

		String tmp = input[id];
		// 모음이면 flag 바꿔서 dfs 진행
		if (tmp.equals("a")||tmp.equals("e")||tmp.equals("i")||tmp.equals("o")||tmp.equals("u")) {
			dfs(id+1, moeum+1, cnt+1, ans+input[id]);
		}
		// 자음이면 그냥 dfs 진행
		else {
			dfs(id+1, moeum, cnt+1, ans+input[id]);
		}
		// 문자를 선택 안 할 경우
		dfs(id+1, moeum, cnt, ans);
		return;
	}
}