본문 바로가기

알고리즘 Algorithm/BOJ 백준 (초급~중급)

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

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

 

1759번: 암호 만들기

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

www.acmicpc.net

 

문제 설명 : 

더보기

바로 어제 최백준 조교가 방 열쇠를 주머니에 넣은 채 깜빡하고 서울로 가 버리는 황당한 상황에 직면한 조교들은, 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

 

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

위키백과, 우리 모두의 백과사전.

ko.wikipedia.org

 

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번: 가르침

첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문

www.acmicpc.net

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

 

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

링크 : https://www.acmicpc.net/problem/1062 1062번: 가르침 남극에 사는 김지민 선생님은 학생들이 되도록이면 많은 단어를 읽을 수 있도록 하려고 한다. 그러나 지구온난화로 인해 얼음이 녹아서 곧 학교

subbak2.tistory.com

 

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;
	}
}
반응형