[Java] 1759번 : 암호 만들기

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

1759번: 암호 만들기

 

처음에 메모리초과 나와서 꽤나 당황했다,,,

 

처음에는 combination 이 아니라 순열을 돌렸기 땜시,,,여기에서 오류가 팡팡팡팡 파라팡~ 나왔다,,,ㅎ

public static void permutation(String arr[], boolean visited[], String output[], int depth, int r) {

        if(depth==r) {
            String str ="";
            for(int i=0;i<r;i++) {
                str+=(output[i]+ "");
            }
            boolean flag=false;
            for(int i=0;i<str.length()-1;i++) {
                if(str.charAt(i) > str.charAt(i+1)) {
                    flag=true;
                }
            }
            if(!flag) {
                sb.append(str).append("\n");
            }
            return;
        }

        for(int i=0;i<arr.length;i++) {
            if(!visited[i]) {
                visited[i] = true;
                output[depth] = arr[i];
                permutation(arr, visited, output, depth+1, r);
                visited[i] = false;
            }
        }

    }

 

두번째 틀린이유는 바로 이 부분이다!

for(int i=0;i<str.length()-1;i++) {
    if (str.charAt(i) > str.charAt(i + 1)) {
        flag=true;
    }
    if(str.charAt(i)=='a' || str.charAt(i)=='e' || str.charAt(i)=='i' || str.charAt(i)=='o' || str.charAt(i)=='u') {
        cnt1++;
    }else {
        cnt2++;
    }
}
if(!flag) {
    if(cnt1>=1 && cnt2>=2) {
        sb.append(str).append("\n");
    }
}

 

str.length()-1 까지만 비교해놔서 마지막 자음, 모음 갯수가 세어지지 않아서였당,,!

함수를 아래처럼 바꿔주고 통과!!!

public static void combination(String arr[], boolean visited[], int start, int depth) {

    if(depth==n) {
        String str="";
        for(int i=0;i<arr.length;i++) {
            if(visited[i]) {
                str+=arr[i];
            }
        }
        boolean flag=false; // 순서 판단
        int cnt1=0, cnt2=0; // cnt1 : 모음, cnt2 : 자음
        // 만약 순서대로가 아니라면 flag 를 바꿔주고 break 해서 나온다!
        for(int i=0;i<str.length()-1;i++) {
            if (str.charAt(i) > str.charAt(i + 1)) {
                flag=true;
                break;
            }
        }
        // 모음, 자음 갯수 세기
        for(int i=0;i<str.length();i++) {
            if(str.charAt(i)=='a' || str.charAt(i)=='e' || str.charAt(i)=='i' || str.charAt(i)=='o' || str.charAt(i)=='u') {
                cnt1++;
            }else {
                cnt2++;
            }
        }
        // flag에 변동이 없다면 순서대로니까, 자음, 모음, 갯수가 맞다면 출력
        if(!flag) {
            if(cnt1>=1 && cnt2>=2) {
                sb.append(str).append("\n");
            }
        }
        return;
    }

    for(int i=start;i<arr.length;i++) {
        if(!visited[i]) {
            visited[i] = true;
            combination(arr, visited, i+1, depth+1);
            visited[i] = false;
        }
    }

}

 

[전체코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static int n, m;
    static String[] cArr;
    static boolean[] visited;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        cArr = new String[m];
        visited = new boolean[m];

        st = new StringTokenizer(br.readLine());
        for(int i=0;i<m;i++) {
            cArr[i] = st.nextToken();
        }
        Arrays.sort(cArr); // 사전 순으로 정렬
        combination(cArr, visited, 0, 0);
        System.out.print(sb);
    }

    public static void combination(String arr[], boolean visited[], int start, int depth) {

        if(depth==n) {
            String str="";
            for(int i=0;i<arr.length;i++) {
                if(visited[i]) {
                    str+=arr[i];
                }
            }
            boolean flag=false; // 순서 판단
            int cnt1=0, cnt2=0; // cnt1 : 모음, cnt2 : 자음
            for(int i=0;i<str.length()-1;i++) {
                if (str.charAt(i) > str.charAt(i + 1)) {
                    flag=true;
                    break;
                }
            }
            for(int i=0;i<str.length();i++) {
                if(str.charAt(i)=='a' || str.charAt(i)=='e' || str.charAt(i)=='i' || str.charAt(i)=='o' || str.charAt(i)=='u') {
                    cnt1++;
                }else {
                    cnt2++;
                }
            }
            if(!flag) {
                if(cnt1>=1 && cnt2>=2) {
                    sb.append(str).append("\n");
                }
            }
            return;
        }

        for(int i=start;i<arr.length;i++) {
            if(!visited[i]) {
                visited[i] = true;
                combination(arr, visited, i+1, depth+1);
                visited[i] = false;
            }
        }

    }

}