(코테) 백준_1759_암호만들기 백트레킹

 

 

 

 

 

처음 제시한 답

package test;

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

public class Backjun_1759 {
	static int L,C;
	static char[] list;
	static char[] result;
	static boolean[] visite = new boolean[26];
	static boolean flag = false;
	static char[] contain = new char[] {'a','e','i','o','u'};
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine()); 
		
		L=Integer.parseInt(st.nextToken());
		C=Integer.parseInt(st.nextToken());				
		
        String[] input = br.readLine().split(" ");
        list = new char[C];
        for (int i = 0; i < C; i++) {
            list[i] = input[i].charAt(0);
        }
		
		result = new char[L];
		
		dfs(0,0);
		
	}

	public static void  dfs(int start , int deep) {
		boolean pass =false;
		if(deep==L ) { //contain 포함되었는지
			for(int i=0;i<5;i++) {
				for(int j=0;j<L;j++) {
					if(contain[i]==result[j]) {
						pass=true;
						break;
					}				
				}
				
			}
			if(pass) {
				for(int i=0;i<L;i++) {
					System.out.print(result[i]);				
				}
				System.out.println("");								
			}
			
		}
		
		
		for(int i=start;i<C;i++) {  //중복제거			
			int index=list[i]-'a';	
			
			if(!visite[index]) {
				visite[index]= true;	
				
				result[deep] = list[i];
				
				dfs(i+1,deep+1);
				
				visite[index]= false;
			}
			
			
			
							//결과값 true 처리.
			
			
		}
		
	}
}

 

 

 

 

 

정석 답 코드 

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

public class Main {
    static int L, C;
    static char[] chars;       // 사용 가능한 문자
    static char[] result;      // 현재 조합 저장

    static final Set<Character> vowels = Set.of('a', 'e', 'i', 'o', 'u');

    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());

        chars = new char[C];
        result = new char[L];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < C; i++) {
            chars[i] = st.nextToken().charAt(0);
        }

        Arrays.sort(chars);  // 오름차순 조합을 위한 정렬

        dfs(0, 0);
    }

    // start: 현재 인덱스, depth: 현재 길이
    public static void dfs(int start, int depth) {
        if (depth == L) {
            if (isValid()) {
                System.out.println(new String(result));
            }
            return;
        }

        for (int i = start; i < C; i++) {
            result[depth] = chars[i];
            dfs(i + 1, depth + 1);
        }
    }

    public static boolean isValid() {
        int vowel = 0, consonant = 0;
        for (char c : result) {
            if (vowels.contains(c)) vowel++;
            else consonant++;
        }
        return vowel >= 1 && consonant >= 2;
    }
}

 

 

 

 

회고.

1. 공백 기준 배열 자르기 

-> String[] input = br.readLine().split(" "); 를 사용하여 공백 포함된 배열 나누지 못했음.

 

2. Set 사용 못하였음 set 을 사용하여 contains으로 간편하게 자음이 포함된지 체크할 수 있다는걸 인지하게 됨. 

 

3. 문제 착각 

-> 자음 1개 이상이면 pass 된다고 실수하였음.  isvalid 함수로 자음 과 모음 갯수를 count 하여 조건에 만족하면 boolean값 리턴하는  좋은 코드를 배웠음.

 

4. 배열을 오름차순으로 정렬하고 시작하지 않았음.

-> Array.sort() 사용하여 오름차순으로 알파벳 정렬을 놓쳤음.