백준 1759번 : 암호 만들기 풀이 및 Java 로 순열, 조합, 부분집합 만들기

www.acmicpc.net/problem/1759

1759번: 암호 만들기

Solution

골드라고 하기엔 많이 쉬운 문제같다. 평소에 조합 짜는 코드를 잘 알고 있다는 가정 하에..

해법은 아주 간단하다. 우선 

3 <= L, C <= 15 로 범위가 굉장히 작고, 중복되는 알파벳 소문자도 없으므로 그냥 별 생각없이 조합 + 완전탐색을 생각했다.

 

1. C개의 chars 중에서 L개의 char 배열인 arr 을 뽑아내야 한다. 조합을 사용하자.

2. 뽑아낸 L개의 배열 중에서 모음의 개수와 자음의 개수를 세어준다. 모음의 종류들을 미리 List 에 저장해두고, 거기 있으면 모음 아니면 자음으로 세면 된다. 모음 최소 1개, 자음 최소 2개 이상이므로 해당 조건을 만족하지 못하면 결과에 출력하지 않는다.

3. 해당 조건 말고는 없으므로, 정렬해서 알파벳 순서로 만들어준 뒤 String 으로 합쳐주면 끝이다.

 

워낙 별 게 없지만, 검색이 제한되는 환경이었다면 조금 고생했을 것 같다.

 

1. 모음 종류를 List 로 만들기

static List<Character> vowelTypes = Arrays.asList('a','e','i','o','u');

List.contains 메서드를 사용하기 위해서 만드려고 했는데, Arrays.asList 는 기억이 났는데 안에 들어가는 매개변수를 { } 로 감싸야하는지, [ ] 로 감싸야하는지 몰라서 둘 다 해봤는데 컴파일 에러가 났었다. 결론은 저렇게 그냥 콤마로 구분해서 넣으면 되더라.

 

2. 조합 코드

꽤 많이 짜왔다고 생각하는데 아직도 한 번씩 헷갈린다. 순열, 조합, 부분집합 코드는 암기를 해서 사용하면 편하다. 시험 환경에서 snippet 으로 저장해둬도 되지만 IDE 가 허용되지 않는 시험에서는 그럼 어떡할 것인가. 외우는게 낫다. 순열, 조합, 부분집합 코드를 저장해둔 것을 공유한다. 필요없다면 넘기자.

import java.util.Scanner;

public class Main {
    static int N, R = 2;
    static int[] nums;
    public static void main(String[] args) {
        System.out.print("입력할 갯수 : ");
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        nums = new int[N];
        for(int i = 0 ; i < N; i++) {
            nums[i] = sc.nextInt();
        }
        System.out.println("1. 조합의 결과");
        makeCombination(0,0,new int[R]);
        System.out.println("2. 순열의 결과");
        makePermutation(0, new int[N], new boolean[N]);
        System.out.println("3. 부분집합의 결과");
        makeSubset(0, new boolean[N]);
    }

    private static void makeCombination(int cnt, int start, int[] arr) {
        if(cnt == R) {
            for(int i = 0 ; i < R; i++) {
                System.out.print(arr[i] + " ");
            }
            System.out.println();
            return;
        }
        for(int i = start; i < N; i++) {
            arr[cnt] = nums[i];
            makeCombination(cnt+1, i+1, arr);
        }
    }

    private static void makePermutation(int cnt, int[] arr, boolean[] visited) {
        if(cnt == N) {
            for(int i = 0 ; i < N; i++) {
                if(visited[i]) System.out.print(arr[i] + " ");
            }
            System.out.println();
            return;
        }
        for(int i = 0 ; i < N; i++) {
            if(visited[i]) continue;
            visited[i] = true;
            arr[cnt] = nums[i];
            makePermutation(cnt + 1, arr, visited);
            visited[i] = false;
        }
    }

    private static void makeSubset(int cnt, boolean[] isSelected) {
        if(cnt == N) {
            for(int i = 0 ; i < N; i++) {
                if(isSelected[i]) System.out.print(nums[i] + " ");
            }
            System.out.println();
            return;
        }
        isSelected[cnt] = true;
        makeSubset(cnt+1, isSelected);
        isSelected[cnt] = false;
        makeSubset(cnt + 1, isSelected);
    }
}

Source Code

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));
    static int L,C;
    static char[] chars;
    static List<Character> vowelTypes = Arrays.asList('a','e','i','o','u');

    static void input() throws IOException {
        StringTokenizer lc = new StringTokenizer(bufferedReader.readLine());
        L = Integer.parseInt(lc.nextToken());
        C = Integer.parseInt(lc.nextToken());
        chars = new char[C];
        StringTokenizer line = new StringTokenizer(bufferedReader.readLine());
        for(int i = 0 ; i < C; i++) {
            chars[i] = line.nextToken().charAt(0);
        }
        Arrays.sort(chars);
    }

    static void checkString(char[] arr) throws IOException {
        int vowels = 0;
        int cons = 0;
        for(int i = 0 ; i < L; i++) {
            if(vowelTypes.contains(arr[i])) {
                vowels++; // 모음 갯수
            } else {
                cons++; // 자음 갯수
            }
        }
        if(vowels < 1 || cons < 2) {
            return;
        }
        Arrays.sort(arr);
        bufferedWriter.write(new String(arr) + " \n");
    }

    static void makeCombination(int cnt, int start, char[] arr) throws IOException {
        if(cnt == L) {
            checkString(arr); // L개의 문자 배열이 완성되면 보낸다.
            return;
        }
        for(int i = start; i < C; i++) {
            arr[cnt] = chars[i];
            makeCombination(cnt+1, i+1, arr);
        }
    }

    static void solve() throws IOException {
        makeCombination(0,0,new char[L]);
    }

    public static void main(String[] args) throws IOException {
        input();
        solve();
        bufferedWriter.close();
        bufferedReader.close();
    }
}