[백준]18119: 단어 암기 - JAVA

[백준]18119: 단어 암기 

18119번: 단어 암기

풀이

🪑 문제는 굉장히 간단하다. 각 쿼리마다 완전히 알고 있는 단어의 개수를 출력하는 문자열 문제이다!

 

📝 문제를 정리해 보쟈.

• 단어는 소문자로만 되어 있으며 단어 안에 모든 알파벳을 알면 그 단어를 안다고 한다.
• 각 쿼리 마다 완전히 알고 있는 단어의 개수를 출력한다.
• 모음은 완벽하게 외웠다. 잊어버릴 일이 없다.

 

 

🙋‍♀️ 처음에는 시간복잡도를 생각해 보았다. 

• O(NM)으로 문자를 하나씩 확인하며 완탐으로 문제를 푼다고 했을때, N의 최대는 10의4제곱, M의 최대는 5X10의4제곱인데 이렇게 되면 최대 O(5X10^8)이 될 것이다. 
• 즉, O(4억)이 되고 시간제한이 4초인 이 문제에서 입, 출력 시간까지 추가되면.. 음.. 이방법이 아닐수도 있겠다 싶었다.
• 그런데 이 문제에서 확인할 수 있는 추가 조건이 있다. 바로 '모음은 완벽하게 외웠다'이다. 따라서 여기서 힌트를 얻고 모음일 경우에 계산하지 않고 continue한다면 완탐으로도 풀 수 있지 않을까 싶어 풀어보았다!

 

 

🔧 문제를 풀어 보쟈!

1. 단어를 입력 받으며 단어 별로 알고 있는 문자를 체크해 준다.
2. 단어 별로 모르는 단어의 개수를 저장하고, 알고 있는 단어인지도 함께 체크한다.
3. 쿼리를 입력 받으며 로직을 수행한다.

 

🔹 단어를 입력 받으며 단어 별로 알고 있는 문자를 체크해 준다.

- 이때 모음인 경우에는 확인하지 않고 넘어간다.

 

🔹 단어 별로 모르는 문자의 개수를 저장하고, 알고 있는 단어인지도 함께 체크한다.

- 처음에는 모르는 단어가 없으므로 0으로 초기화 한다.

- 처음에는 모든 단어를 알고 있으므로 true로 초기화 한다.

 

🔹 쿼리를 입력 받으며 로직을 수행한다.

- 마찬가지로 모음인 경우에는 확인하지 않고 넘어간다.

- 1을 입력받은 경우에는 단어에 해당 알파벳이 포함된다면 모르는 알파벳 개수를 증가시킨다. 기존에 알고 있었던 단어라면 모르는 단어로 변경해주고 전체 결과에 해당하는 수를 감소시킨다.

- 2를 입력받은 경우에는 이미 알고 있는 단어는 계산해줄 필요가 없으므로 넘어가고, 해당 알파벳을 포함한 단어를 확인한다. 모르는 알파벳의 개수를 줄여준 다음 모르는 알파벳이 0개가 되면 해당 단어를 알게 되므로 전체 경우의 수를 증가시키고 아는 단어로 변경해 준다.

 

 

코드

import java.io.*;
import java.util.*;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
 
        //입력
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
 
        String str = bf.readLine();
        StringTokenizer st = new StringTokenizer(str);
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
 
        boolean[][] word_check = new boolean[n][26]; // 단어의 알파벳 별로 알고 있는지 여부 체크
        int[] forget_count = new int[n]; // 각 단어 별로 모르는 단어 개수 저장
        boolean[] knwon_check = new boolean[n]; // 알고 있는 단어인지 체크
        for(int i = 0; i < n; i++) {
            str = bf.readLine();
            for(int j = 0; j < str.length(); j++) {
                char c = str.charAt(j);
                if(c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') continue; //모음 피료없어
                word_check[i][c - 'a'] = true; //처음에는 모든 단어 알고 있음.
            }
            knwon_check[i] = true;
        }
 
        StringBuilder sb = new StringBuilder();
        int result = n;
        for(int i = 0; i < m; i++) {
            str = bf.readLine();
            st = new StringTokenizer(str);
            char code = st.nextToken().charAt(0);
            char alpha = st.nextToken().charAt(0);
            //입력 끝
            if(alpha == 'a' || alpha == 'e' || alpha == 'i' || alpha == 'o' || alpha == 'u') continue;
 
            if(code == '1') {
                for(int j = 0; j < n; j++) {
                    if(word_check[j][alpha - 'a']) {
                        forget_count[j]++;
                        if(knwon_check[j]) {
                            knwon_check[j] = false;
                            result--;
                        }
                    }
                }
            } else {
                for(int j = 0; j < n; j++) {
                    if(knwon_check[j]) continue;
                    if(word_check[j][alpha - 'a']) {
                        forget_count[j]--;
                        if(forget_count[j] == 0) {
                            knwon_check[j] = true;
                            result++;
                        }
                    }
                }
            }
            sb.append(result + "\n");
        }
        System.out.println(sb.toString());
    }     
}