알고리즘/백준

공부 170일차: 백준 1759번 암호 만들기 자바 java

김발자~ 2023. 1. 16. 15:54
반응형

1759 암호 만들기

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

 

1759번: 암호 만들기

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

www.acmicpc.net

 

 

 

 

백준 1759번 문제 암호 만들기

문제

 

 

 

 

과정 생각해보기

 

https://gimbalja.tistory.com/297

 

공부 157일차: 백준 15655번 N과 M (6) 자바 java

15655 N과 M (6) https://www.acmicpc.net/problem/15655 15655번: N과 M (6) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는

gimbalja.tistory.com

참고하면 좋을 문제

 

 

 

정답 인정 코드

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
import java.io.*;
import java.util.*;
 
public class Main {
    
    static int l, c;
    static char[] arr;
    static char[] alphabet;
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
    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());
        
        alphabet = new char[c];
        arr = new char[l];
        
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < c; i++) {
            alphabet[i] = st.nextToken().charAt(0);
        }
 
        Arrays.sort(alphabet);    // 사전순 정렬을 위해
        DFS(0, 0);
        bw.flush();
        bw.close();
    }
    
    static void DFS(int start, int depth) throws IOException {
        if(depth == l) {
            if(condition()) {    // 모음/자음 조건 일치 여부
                for(char ch : arr) {
                    bw.write(ch+"");
                }
                bw.newLine();
            }
            return;
        }
        
        for(int i = start; i < c; i++) {
            arr[depth] = alphabet[i];
            DFS(i+1, depth+1);    // 오름차순(메인 메서드에서 사전순 정렬 후 가능)
        }
    }
    
    // 모음/자음 검사
    static boolean condition() {
        int vowelsCnt = 0;
        int consonantsCnt = 0;
        for(int i = 0; i < l; i++) {
            if(arr[i] == 'a' || arr[i] == 'e' || arr[i] == 'i' || arr[i] == 'o' || arr[i] == 'u') {
                vowelsCnt++;
            } else {                
                consonantsCnt++;
            }
        }
        if(vowelsCnt >= 1 && consonantsCnt >= 2) {
            return true;
        }
        return false;
    }
}
 cs

 

과정 설명과 주석을 보면 이해할 수 있을 것이다

 

 

 

 

DFS 문제는 무궁무진한 듯하다

반응형