<Algorithm> 186. 가르침(BJO)

1. 1062번 가르침(BJO)

   사용 알고리즘 : 완전탐색(조합) 

• 놓친부분도 많았고 이걸 찾아서 고쳐도 메모리 초과가 계속 발생해 분노한 문제 

• 핵심이 인사말을 무조건 알아야 된다는 걸 놓친 것 같다. 인사말을 빼는게 아닌 포함해서(무조건 배워야함) 구해야 한다.

• 메모리초과 부분은 String을 int로 바꿨더니 해결되었다. String은 char 배열로 볼 수 있고 즉 문자당 2Byte의 메모리를 가진다.

• 이문제는 최대 (27-5)!/10!에 연산을 가지므로 String을 사용했을시 메모리가 꽤 많이 발생하기 때문에 시간 초과가 발생한 것 같다.

문제에 대한 접근&생각

1. 알파벳을 배워서 최대 몇개 맞출 수 있나 -> 완전탐색 -> a b c와 c b a는 같다 -> 조합! 

내 코드 

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

import java.util.Scanner;          public class Main {         static int n,k;         static String words[];         static char[] alpa;         static boolean visited[];         public static void main(String[] args) {             Scanner sc = new Scanner(System.in);             n = sc.nextInt();             k = sc.nextInt();             sc.nextLine();             /***************************              * 배울 수 있는 글자수를 완전탐색하여              * 주어진 글자를 읽을 수 있는지 판단              * 하고 그 최댓값을 구한다.              ***************************/             words = new String[n];             for(int i = 0; i < n; i++) {                 String temp = sc.nextLine();                 words[i] = temp.substring(4, temp.length()-4);             }             if (k < 5) {                 System.out.println(0);                 return;             }             visited = new boolean[26];             visited['a'-97] = visited['t'-97]= visited['c'-97]= visited['i'-97]= visited['n'-97] = true;             brute(5,97);             System.out.println(max);         }         static int max =0;         public static void brute(int deep,int idx) {             if(deep == k) {                 int count = 0;                 loop:for(int i = 0; i < words.length; i++) {                     char[] ch = words[i].toCharArray();                     for(int j = 0; j < ch.length; j++) {                         if(!visited[ch[j]-97]) continue loop;                     }                     count++;                 }                                  max = Math.max(max, count);                 return;             }             for(int i = idx; i <= 122; i++) {                 if(!visited[i-97]) {                     visited[i-97] = true;                     brute(deep+1, i+1);                     visited[i-97] = false;                 }             }         }     }   Colored by Color Scripter

cs

 

얻은 것

• 조합 탐색 할때는 그냥 +1 아니라 지금 순서(i)에 대해 +1을 해주어야 1 2 3 , 1 2 4 , 2 3 4  처럼 중복이 발생하지 않는다. !!!!!