[백준] 1759번 - "암호 만들기" (Java)

www.acmicpc.net/problem/1541www.acmicpc.net/problem/1759

1759번: 암호 만들기

---

 

난이도 : 골드5

조합과 브루트포스 연습용으로 좋은 문제인 것 같습니다.

 

문제에 주어진 대표적인 조건에 맞춰서 문제를 해결해 나가면 풀 수 있습니다.

1. 알파벳이 암호에서 증가하는 순서.

2. 최소 한 개의 모음, 최소 두 개의 자음.

 

첫 번째 조건은 Arrays.sort()로 해결하였습니다.

 

두 번째 조건은 주어진 입력 L길이의 맞게 암호가 구성되어지면 전역 변수에 따로 만들어둔

모음 배열(vowe[])을 각 암호(알파벳)가 탐색하여 모음이면 모음 변수에 ++, 자음이면 자음 변수에 ++해주었습니다. 

 

시간 제한은 2초입니다. 2초이면 약 2억개의 데이터 안에서  문제를 해결할 수 있습니다. 

해당 문제는 C가지의 알파벳이 주어지고, L가지의 알파벳을 선택하면 됩니다.

 

주어진 알파벳을 "사용한다", "사용하지 않는다"로 결정한다면 알파벳당 2가지의 선택이 있는 것입니다. 

이러한 선택이 C가지가 있는 것이므로, 2^C의 시간 복잡도를 가질 수 있습니다.

 

문제의 C조건은 3<= L <= C <= 15이므로, 최악의 시간 복잡도는 2^15 = 32678입니다. 

모든 경우의 수를 다 구해봐도 충분히 주어진 시간 복잡도 내에서 풀 수 있는 문제입니다.

 

 

- void main()

입력을 받아오고 전역 변수들을 초기화 및 선언해줍니다.

문제에서 사전순으로 증가하게끔 출력하는 조건이 있어 Arrays.sort()를 사용하여 사전순(오름차순)으로

입력 받은 배열을 변환해줍니다.

 

- void recursion()

재귀 호출로 모든 원소에 접근하도록 했습니다.  하지만 인자로 int start를 두어,

암호인 알파벳이 사전순으로 증가하는 방향으로 반복문의 시작 인덱스로 설정하기 위해서 

현재 호출된 알파벳의 다음 인덱스로 또 다시 재귀 호출 하도록 했습니다.

 

이렇게 하면 사전순으로 모든 알파벳들을 탐색하게 됩니다.

depth가 L과 같을 경우, 알파벳 당 모음/자음 판별을 하여 StringBuilder에 넣게끔 하였습니다.

 

- boolean check()

문제에서 주어진 두 번째 대표 조건을 확인하는 메소드입니다.

모음과 자음의 갯수를 확인한 뒤, true 혹은 false를 반환합니다. 

 

 

 

  코드

public class BOJ_1759 {
	// BOJ / 1759번 / 암호 만들기 / 조합, 백트래킹  / 골드5
	static int l, c;
	static String print[], alp[];
	static StringBuilder sb;
	static String vowel[] = {"a","e","i","o","u"};
    
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
		
		l = Integer.parseInt(stk.nextToken());
		c = Integer.parseInt(stk.nextToken());
		alp = br.readLine().split(" ");
		print = new String[l];
		sb = new StringBuilder();
		
		// 사전순으로 증가.
		Arrays.sort(alp);

		recursion(0,0);
		
		System.out.println(sb);
	}
	
	public static void recursion(int depth, int start) {
		
		// l개를 선택했으면 
		if(depth == l) {
			// 자음 모음 조건 확인
			if(check()) {
				for(String value : print) {
					sb.append(value);
				}
				sb.append("\n");
			}
			
			return;
		}
		
		//visit 배열은 따로 필요가 없다. 어차피 오름차순 정렬이고 
		// 다음 인덱스를 재귀의 start인자로 받아주면 되기 때문.
		for(int i=start; i<alp.length; i++) {
			print[depth] = alp[i];
			recursion(depth+1, i+1);
		}
	}

	public static boolean check() {
		int vow = 0; // 모음
		int cons = 0; // 자음
		
		for(String value : print) {
			boolean isVowel = false;
			// 모음이면 vow++
			for(int i=0; i<vowel.length;i++) {
				if(value.equals(vowel[i])) {
					isVowel = true;
					vow++;
				}
				if(isVowel) {
					break;
				}
			}
			// 자음이면 cons++;
			if(!isVowel) cons++;
			
			// 조건에 맞으면 return;
			if(vow >= 1 && cons >= 2) {
				return true;
			}
		}
		
		return false;
	}
}

 

피드백은 얼마든지 환영합니다.