백준 18119번 단어 암기

 

 

 

문제 보러가기 :  https://www.acmicpc.net/problem/18119 

 

 

 

18119번: 단어 암기

 

 

이번 문제는 비트 마스킹 문제였습니다. 

 

정수의 2진수 표현을 자료구조로 쓰는 기법을 비트 마스킹이라고 합니다.    

비트 마스킹 기법을 활용하여 문제를 풀면 시간 단축, 메모리 절약을 할 수 있습니다.

문제 풀이를 하기 전에 문제를 풀 때 사용했던 비트 연산자들을 테이블로 정리했습니다.

 

 

 

 

비트 연산자

 

연산자	설명	예시
a << b	a를 b 비트만큼 왼쪽으로 shift	1 << 2 → 0100 (4)
a & b	두 비트가 1이라면 1	1100 & 1011 → 1000
a | b	하나라도 1이면 1	1100 | 1011 → 1111
a ^ b	두 비트가 다르면 1	1011 ^ 1011 → 0000

 

 

 

《문제 풀이》

 

1. 처음에는 모든 알파벳을 기억하는 상태이므로 remember 변수를 초기화 (2^0 ~ 2^25까지 더하기) 

2. 사전에 적혀있는 N가지 단어들을 배열에 기록 (단어에 중복 알파벳이 있을 수 있으므로 += 연산자를 사용하면 안됨)

3. XOR 연산자를 사용하여 문자 x를 잊기

   --> 잊었던 문자를 다시 기억한다면 해당 문자 - 'a' 위치는 다시 1로 채워짐 

4. remember AND 문자열을 수행하여 나온 결과가 문자열의 비트와 같다면 카운트

 

 

 

《C++ 코드》

 

#include <bits/stdc++.h>

using namespace std;

int word[10000];

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N, M;
	cin>>N>>M;
	
	int remember = 0;
	
	// 처음에는 모든 알파벳을 기억하는 상태  
	for(int i=0; i<26; i++) {
		remember += (1 << i);
	}

	for(int i=0; i<N; i++) {
		string s;
		cin>>s;
		
		// 배열에 문자열 기록 
		// ex) apple 1000 1000 0001 0001   
		for(int j=0; j<s.length(); j++) {
			word[i] |= (1 << (s[j] - 'a'));
		}
	}
	
	int o;
	char x;
	
	for(int i=0; i<M; i++) {
		int cnt = 0;
		cin>>o>>x;
		
		// o: 1 -> x를 잊기
		// o: 2 -> x를 기억하기    
		remember ^= (1 << (x - 'a'));
		
		for(int j=0; j<N; j++) {
			
			// remember AND 단어 
			if((remember & word[j]) != word[j])
				continue;
			
			cnt++;
		}
		cout<<cnt<<"\n";
	}
	
	return 0;
}

 

 

개발 환경: Dev-C++

 

 

baekjoon - 정답 화면