[BOJ] 백준 18119번 : 단어 암기 (JAVA)

문제

준석이는 영어 단어를 외우려고 한다. 사전에는 N가지 단어가 적혀 있다. 모든 단어는 소문자이다. 단어 안에 있는 모든 알파벳을 알 때, 그 단어를 완전히 안다고 한다.

다음과 같은 쿼리들이 주어진다.

• 1 x : 알파벳 x를 잊는다.
• 2 x : 알파벳 x를 기억해 낸다.

처음에 모든 알파벳을 기억하는 상태고, 모음은 완벽하게 외웠기 때문에 절대 잊지 않는다.

각 쿼리마다 완전히 알고 있는 단어의 개수를 출력하여라.

 

 

입력

첫 번째 줄에는 정수 N (1 ≤ N ≤ 104)과 M (1 ≤ M ≤ 5×104)이 주어진다.

다음 N개의 줄에는 문자열이 하나씩 주어진다. 문자열의 길이는 103을 넘지 않는다.

다음 M개의 줄에는 정수 o와 문자 x가 한 줄씩 주어진다. o는 1, 2중 하나이고, x는 알파벳 소문자이다.

o가 1이면 x를 잊는다는 뜻이고, o가 2면 x를 기억해낸다는 뜻이다. o가 1일 때는 x를 기억하고 있었음이 보장되고, o가 2일 때는 x를 잊고 있었음이 보장된다.

 

 

출력

각 쿼리마다 정수 하나를 출력한다.

 

 

풀이

골드4치고는 조금 어려웠던 브루트포스 문제였습니다. 저는 처음에 단순하게 쿼리가 들어올 때마다 모든 단어 목록을 검사해서 기억하는 단어 개수를 세려고 했으나, 시간 초과를 피할 수 없었습니다.

 

그래서 브루트포스를 하되, 조금 더 똑똑한 방식을 사용해야만 하였습니다. 전반적인 로직은 아래와 같습니다.

 

 

1. 단어 목록을 입력받을 때, 각 단어마다 해당되는 알파벳을 true로 표시하도록 boolean 타입 배열을 정의한다.

 

2. 각 단어마다 모든 알파벳을 기억하고 있는지 확인하는 boolean 타입 배열과 잊어버린 알파벳의 개수를 int 타입 배열로 정의한다. (전자는 valid, 후자는 cnt로 정의하였습니다.)

 

3. 현재 모든 알파벳을 알고 있는 상황이므로 ans = N으로 정의한다.

 

4. 쿼리를 입력받는다.

 

4-1. 쿼리의 o가 1일 경우

만약, 현재 잊어버릴 알파벳이 단어 목록의 i번째 단어에 해당할 경우, cnt[i]를 1 증가시키고, valid[i]가 true라면, ans를 1 감소시킨다. 그리고 valid[i] = false로 초기화한다.

 

4-2. 쿼리의 o가 2일 경우

만약, 기억하려는 알파벳이 단어 목록의 i번째 단어에 해당하고, 그 단어가 해당하는 단어의 모든 알파벳을 기억하고 있지 못할 경우, cnt[i]를 1 감소시킨다. 이 때, cnt[i]가 0이라면, 모든 알파벳을 기억하게 되었으므로 valid[i] = true로 초기화하고, ans를 1 증가시킨다.

 

5. 4번 과정을 반복하면서 ans를 출력한다.

 

아래는 위 과정을 정리한 소스코드입니다.

 

 

소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
 
        boolean[][] words = new boolean[N][26];
        for (int i = 0; i < N; i++) {
            String input = br.readLine();
 
            for (int j = 0; j < input.length(); j++) {
                char c = input.charAt(j);
 
                words[i][c - 'a'] = true;
            }
        }
 
        boolean[] valid = new boolean[N]; // 각 단어마다 모든 알파벳을 기억하고 있는지 확인.
        Arrays.fill(valid, true);
 
        int[] cnt = new int[N]; // 각 단어마다 잊어버린 알파벳의 개수.
 
        StringBuilder sb = new StringBuilder();
        int ans = N; // 모두 다 기억한 상태에서 시작.
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int o = Integer.parseInt(st.nextToken());
            char x = st.nextToken().charAt(0);
 
            if (o == 1) {
                for (int j = 0; j < N; j++) {
                    // 잊어버릴 알파벳이 단어 목록에 속해 있을 경우
                    if (words[j][x - 'a']) {
                        cnt[j]++;
                        if (valid[j]) {
                            ans--;
                            valid[j] = false;
                        }
                    }
                }
            } else if (o == 2) {
                for (int j = 0; j < N; j++) {
                    // 기억하려는 알파벳이 단어 목록에 속해 있고, 모든 알파벳을 기억한 단어가 아닐 경우.
                    if (!valid[j] && words[j][x - 'a']) {
                        cnt[j]--;
 
                        if (cnt[j] == 0) {
                            valid[j] = true;
                            ans++;
                        }
                    }
                }
            }
 
            sb.append(ans + "\n");
        }
 
        bw.write(sb.toString() + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}

 

 

주의 사항

위의 풀이에서는 valid와 cnt를 배열로 따로 분리하였으나, 저는 원래 처음에 Word라는 클래스 내에서 알파벳 배열과 valid, cnt를 따로 정의하였습니다.

 

그러나, 이 방식은 시간초과를 불러왔습니다. 문제에서는 시간 제한이 4초였고, 어떤 언어든 추가 시간을 주지 않는 것으로 보입니다. 아마, 클래스로 정의하는 것은 메인 함수에서 new라는 키워드를 이용하여 새로운 메모리를 할당하는 과정이 시간을 잡아먹지 않았나 추측하고 있습니다.

 

슬프게도 이 문제를 같이 풀었던 제 친구는 저와 같은 로직인데 c++이어서 클래스로 통과가 되었습니다. 꼬우면 c++을 하는 것이 맞지만, java를 계속 할 입장에서 이런 상황은 조금 억울해도, 객체 생성이 생각보다 시간이 많이 소요된다는 사실을 안 것은 꽤 의미가 있던 것 같습니다.

 

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.