백준 1759번: 암호 만들기

문제

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

1759번: 암호 만들기

 

---

풀이

서로 다른 c개의 알파벳 소문자들을 사용하여 길이가 l인 다음 규칙을 만족하는 암호의 모든 경우를 출력하는 문제입니다.

1. 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다.
2. 알파벳이 암호에서 증가하는 순서로 배열되어있다.

---

코드

C언어

l과 c를 입력받은 후에 c개의 서로 다른 알파벳을 입력받기 전에 개행과 띄어쓰기를 표현하기 위해 getchar()를 사용했습니다.

모든 입력이 끝나면 qsort를 이용하여 입력받은 알파벳이 들어있는 배열 password를 암호에서 2번 조건을 만족해야 하기 때문에 정렬한 뒤에 dfs 함수를 실행합니다.

dfs 함수 내부에서 i를 포함한 for문은 2번 조건을 만족하기 위해 idx부터 시작하여 추후에 dfs 함수를 재귀적으로 실행할 때 i + 1을 매개변수로 합니다. arr[dpth] = password[i]를 통해 해당 알파벳을 앞에서 사용했음을 표시합니다.

dpth가 l이 되면 길이가 1번 조건을 만족하는지 i를 포함한 for문 안의 switch문을 통해 확인합니다. 만족한다면 arr를 출력합니다. 이때 무조건 password의 앞쪽에서부터 탐색하기 때문에 암호는 문제의 조건에 맞게 사전식으로 출력됩니다.

#include <stdio.h>
#include <stdlib.h>
int l, c;
char *arr, *password;
int compare(const void* a, const void* b) {
	char o1 = *(char*)a;
	char o2 = *(char*)b;
	if (o1 > o2) return 1;
	else if (o1 < o2) return -1;
	else return 0;
}
void dfs(int dpth, int idx) {
	if (dpth == l) {
		int vowel = 0, consonant = 0;
		for (int i = 0; i < l; i++) {
			switch (arr[i]) {
			case 'a': case 'e': case'i': case'o': case'u':
				vowel++;
				break;
			default:
				consonant++;
				break;
			}
		}
		if (vowel > 0 && consonant >= 2) {
			printf("%s\n", arr);
		}
		return;
	}
	for (int i = idx; i < c; i++) {
		arr[dpth] = password[i];
		dfs(dpth + 1, i + 1);
	}
}
main() {
	scanf("%d %d", &l, &c);
	password = (char*)malloc(sizeof(char) * c);
	arr = (char*)malloc(sizeof(char) * c);
	for (int i = 0; i < c; i++) {
		getchar();
		scanf("%c", &password[i]);
	}
	qsort(password, c, sizeof(char), compare);
	dfs(0, 0);
}

자바

위의 C언어를 이용한 풀이와 동일한 방법으로 pasword를 정렬할 때 java.util.Arrays 클래스의 sort 메서드를 사용했고, Stringbuilder를 이용하여 한꺼번에 출력했습니다.

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.Arrays;

public class Main {

    static int l, c;
    static char[] arr, password;
    static StringBuilder sb = new StringBuilder();

    public static void dfs(int dpth, int idx) {
        if (dpth == l) {
            int vowel = 0, consonant = 0;
            for (int i = 0; i < l; i++) {
                switch (arr[i]) {
                    case 'a': case 'e': case 'i': case 'o': case 'u':
                        vowel++;
                        break;
                    default:
                        consonant++;
                        break;
                }
            }
            if (vowel > 0 && consonant >= 2) {
                sb.append(arr).append("\n");
            }
            return;
        }
        for (int i = idx; i < c; i++) {
            arr[dpth] = password[i];
            dfs(dpth + 1, i + 1);
        }
    }

    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());
        arr = new char[l];
        password = new char[c];
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < c; i++) {
            password[i] = st.nextToken().charAt(0);
        }
        Arrays.sort(password);
        dfs(0, 0);
        System.out.print(sb);
    }
}

 

---

결론

처음에 이 문제에 해결할 때 dfs 함수의 매개변수로 idx를 사용하지 않고 i를 이용한 for문 안에 다음과 같이 적었습니다.

for (int i = 0; i < c; i++) {
	if (!visited[i]) {
		if (dpth > 0 && arr[dpth - 1] > password[i]) continue;
		visited[i] = 1;
		arr[dpth] = password[i];
		dfs(dpth + 1);
		visited[i] = 0;
	}
}

정답 처리는 되었지만 블로그에 글을 쓰면서 문제와 제 코드를 다시 한번 읽어보면서 이전에 작성했던 코드에서는 password를 정렬할 필요도 없었고 굉장히 비효율적임을 알게 되었고 수정하여 글을 작성하였습니다.