[백준] 18119 단어암기

📌 문제

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

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

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

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

✔ 입력

첫 번째 줄에는 정수 N (1 ≤ N ≤ 10^4)과 M (1 ≤ M ≤ 5×10^4)이 주어진다.
다음 N개의 줄에는 문자열이 하나씩 주어진다. 문자열의 길이는 10^3을 넘지 않는다.
다음 M개의 줄에는 정수 o와 문자 x가 한 줄씩 주어진다. o는 1, 2중 하나이고, x는 알파벳 소문자이다.
o가 1이면 x를 잊는다는 뜻이고, o가 2면 x를 기억해낸다는 뜻이다. o가 1일 때는 x를 기억하고 있었음이 보장되고, o가 2일 때는 x를 잊고 있었음이 보장된다.

✔ 접근방법

문제만 봤을 때는 크게 어렵게 느껴지지 않는다. 하지만, M개의 쿼리마다 N개의 정수를 체크한다고 생각하면 5x10^4 * 10^4로 5억이상의 연산이 필요한데... 제한시간은 4초이다. 일반적인 탐색으로는 문제를 풀이할 수 없다.

'비트마스크'를 활용하면 풀이가 훨씬 가능해진다.
알아두어야 할 연산은 다음과 같다.

int alph = (1 << 27) - 1 

• 1을 27만큼 왼쪽 시프트 연산을 수행하면 27번째 자리만 1이고 나머지가 0인 비트가 생성된다.
  이 때, 1을 빼주면 비트가 모두 1인 26자리 비트가 생성된다.
  
  
  

cur |= 1 << ('c' -'a');

• 현재 값을 cur이라 할때, 현자 값에서 ( 'c' - 'a') 의 값은 3으로 1 << ('c' - 'a')의 값은 1000이 된다.
  이 값을 cur과 |(or)연산 하게 되면 현재 값에서 c의 자리가 1로 변경된다.
  문제에선, 입력된 알파벳 값이 포함되어 있다는 것을 의미한다.

alph &= ~(1 << (target-'a')); 

• target 알파벳 값을 ~(not) 연산하면 target 알파벳의 비트자리 값이 0으로 변경되고 나머지는 1로 변경된다.
  이 값과 alph값을 &(and)연산하면 해당하는 target알파벳 값의 자리 비트가 0으로 변경된다.
  문제에선, 값을 잊은 것으로 표시한다.

✔ 코드

import java.util.Scanner;

//단어 암기
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		//문자열의 수
		int n = sc.nextInt();
		//쿼리 의 수
		int m = sc.nextInt();
		
		//1로 초기화된 26자리 비트
		int alph = (1 << 27) - 1;
		
		//단어를 담는 배열
		int[] words = new int[n];
		
		for(int i = 0; i < n; i++) {
			String word = sc.next();
			// 각단어의 알파벳 위치만 1로 변경
			for(char c : word.toCharArray())
				words[i] |= 1 << (c -'a');
		}
		
		for(int i = 0; i < m; i++) {
			int o = sc.nextInt();
			char target = sc.next().charAt(0);
			
			//잊는다
			if(o == 1) {
				//target위치의 값만 0으로 바꾸고 & 연산자를 통해 그 부분의 alph비트 값을 0으로 변경
				alph &= ~(1 << (target-'a')); 
			}
			//기억한다
			else {
				alph |= (1 << (target-'a')); 
			}
			
			int count = 0;
			for(int j = 0; j < words.length; j++) {
				//alph와 word연산한 값이 word보다 같거나 크면 모든 알바펫을 알고 있는 것으로 단어를 아는 것.
				if((alph & words[j]) >= words[j]) {
					count++;
				}
			}
			System.out.println(count);
			
		}
	}
}

🖋 회고

비트 연산에 대해서 잘 알고 있다면 쉽게 풀 수 있는 문제지만, 익숙치 않아 비트 연산에 대해 한번 복습하는 시간을 가질 수 있었다.
비트 연산을 수행하지 않고 배열을 생성하여 위에 로직과 동일하게 수행하도록 코드를 작성할 수도 있는데 그럴 경우 더욱 복잡해지므로 비트연산을 활용하는 코드로 작성하였다.

출처 : https://www.acmicpc.net/problem/18119