[백준/JAVA] 1062번: 가르침

🔺 문제

1062번: 가르침

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int n, k;
    static int max = 0;
    static boolean[] visited = new boolean[26];
    static String[] words;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        
        words = new String[n];
        for(int i = 0 ; i < n ; i++) {
            words[i] = br.readLine();
            words[i] = words[i].replace("anta", "").replace("tica", "");
        }
        
        if(k < 5) {         // a n t i c 개수 (= 5개)
            System.out.println(0);
            return;
        }
        else if(k == 26) {  // 모든 알파벳 다 가능
            System.out.println(n);
            return;
        }
        
        visited = new boolean[26]; // 각 알파벳 배웠는지 확인
        // a n t i c은 미리 처리
        visited['a' - 'a'] = true;
        visited['n' - 'a'] = true;
        visited['t' - 'a'] = true;
        visited['i' - 'a'] = true;
        visited['c' - 'a'] = true;
        
        // 조합 -> dfs
        backtracking(0, 0);
        System.out.println(max);
    }
    
    public static void backtracking(int alpha, int len) {
        if(len == k - 5) {  // a n t i c 제외한 조합
            int cnt = 0;
            
            // 단어만큼 반복
            // 뽑은 알파벳으로 몇 개의 단어를 읽을 수 있는지 카운트
            for(int i = 0 ; i < n ; i++) {
                boolean isValid = true;
                
                // 단어 한 개씩 비교해서 단어 포함하는지 비교
                for(int j = 0 ; j < words[i].length() ; j++) {
                    if(!visited[words[i].charAt(j) - 'a']) {
                        // 배우지 않은 알파벳이 있는 경우
                        isValid = false;
                        break;
                    }
                }
                if(isValid) cnt++;
            }
            max = Math.max(max, cnt);
            return;
        }
        
        // 알파벳 돌면서 가능한 조합 찾기
        for(int i = alpha ; i < 26 ; i++) {
            if(!visited[i]) {
                visited[i] = true;
                backtracking(i, len + 1);
                visited[i] = false;
            }
        }
    }
}

✅ 해결 아이디어
✔ 백트래킹 & 조합 (k - 5개)

 

---

🔺 다른 풀이들

- 풀이 굿..

[Algorithm] 백준 1062 가르침 java

 

 

- 비트 마스킹 사용... 😵

백준 1062번: 가르침 (JAVA)

 

---

💬 느낀 점

후엥 어렵구나...

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

 

[백준]1062: 가르침 - JAVA

[Java] [백준 1062][백트랙킹,비트마스크] 가르침