백준 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를 잊고 있었음이 보장된다.

출력

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

 

---

 

내 풀이

N개의 단어, M개의 명령. 총 몇 개의 단어를 기억하고 있는지 count에 저장한다.

각 단어마다, 해당 알파벳이 사용되는지를 2진수로 저장하였다. (letterTable: int[N])

또한, 각 단어마다 몇 개의 알파벳을 잊어버렸는지 확인할 수 있는 int[N] array letterForgot를 선언하였다.

만약 까먹는 명령이 나왔을 경우, i를 N개의 단어에 대해 for문을 돌면서 비트연산을 통해 알파벳이 해당 단어에서 사용되는지 체크한 후, 만약 사용된다면 letterForgot[i]을 하나 늘렸다. 그러고 letterForgot[i]이 1이라면, 그 알파벳을 까먹으면서 i번째 단어를 까먹은 것이므로 count를 1 빼준다. 문제 조건에서 까먹는 명령이 올 때에는 반드시 그 알파벳을 기억하고 있는 상태였다는 것이 보장되기에 사용할 수 있는 알고리즘이다.

만약 기억하는 명령이 나왔을 경우, 마찬가지로 for문을 돌면서 해당 알파벳이 사용되면 letterForgot[i]를 1 빼주며, letterForgot[i]가 0이 된다면 그 알파벳을 기억하게되면서 단어도 기억하게 되는 것이므로 count를 1 더해준다. 마찬가지로 문제 조건에서 기억하는 명령이 올 때에는 그 알파벳을 까먹은 상태였다는 것이 보장되기에 동작하는 알고리즘이다.

 

배운 점

O(MN) 알고리즘인데 MN이 최대 4억번이다. 그리고 시간 제한이 4초이고, 컴퓨터가 대략 1초에 3~5억번 연산을 한다고 들었으므로(바킹독 선생님 블로그) 가능하다고 생각했다. 다만 그 연산이 비효율적일 경우는 안 되더라.

문제를 실전처럼 풀어보기 위해 분류를 안 보고 접하였고, 그래서 letterTable을 boolean[][] 배열로 저장했는데, 단순히 memory complexity뿐만 아니라 연산 시간에서도 문제가 있었다.

앞으로도 시간 제한에 간당간당하게 걸리는 문제는 비트마스킹을 활용할 여지가 있는지 살펴볼 필요가 있어 보인다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException{
		StringBuilder sb = new StringBuilder();
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		int count = 0; // 기억하는 단어 개수
		int[] letterForgot = new int[N]; // 단어별 까먹은 글자 개수 
		int[] letterTable = new int[N]; // 단어별 쓰인 알파벳을 2진수로 기록
		String str;
		
		for (int i = 0; i < N; i++) {
			str = br.readLine();
			int temp = 0;
			for (int j = 0; j < str.length(); j++) {
				temp |= (1<<(str.charAt(j)-'a'));
			}
			letterTable[i] = temp;
			count++;
		}
		
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int command = Integer.parseInt(st.nextToken());
			int letter = st.nextToken().charAt(0) - 'a';
			
			if (command == 1) { // 까먹었다면
				for (int j = 0; j < N; j++) {
					if ((letterTable[j] & (1<<letter)) == 0) continue; 
					if (letterForgot[j]++ == 0) count--;
				}
			}
			else { // 기억해낸다면
				for (int j = 0; j < N; j++) {
					if ((letterTable[j] & (1<<letter)) == 0) continue; 
					if (letterForgot[j]-- == 1) count++;
			
				}
			}
			
			sb.append(count+"\n");
		}
		System.out.println(sb.toString());
	}

}