반응형
문제링크: https://www.acmicpc.net/problem/18119
18119번: 단어 암기
준석이는 영어 단어를 외우려고 한다. 사전에는 N가지 단어가 적혀 있다. 모든 단어는 소문자이다. 단어 안에 있는 모든 알파벳을 알 때, 그 단어를 완전히 안다고 한다. 다음과 같은 쿼리들이 주
www.acmicpc.net
굳이 따지면 브루트포스보다도 비트마스킹이 핵심인 문제!
접근방식
1. 일반적인 방식이라면, 알파벳 배열을 하나 만들고 입력되는 알파벳을 지원주거나 다시 채워주며 진행
2. 그리고 문자별로 string size만큼 반복하며 가능한지 확인하는 방식
3. 근데 이렇게 해결하면 시간복잡도가 O(10^4 * 10^4 * 10^3) 로 무조건 시간초과
4. 비트마스킹을 통해서 문자들을 한번에 확인하는 O(10^4 * 10^4) 방식으로 문제를 해결
문제풀이
1. int remember에 비트에 알파벳(0~25)값들을 마킹한다.
ex) 'a'는 0000 0001 이렇게 마킹한거고, 'b'는 0000 0010 여기에 마킹한거!
for (int i = 0; i < 26; i++)
remember |= (1 << i);2. 각 문자 단어들을 1번과 같은 방식으로 포함된 알파벳을 마킹한다.
for (int j = 0; j < temp.size(); j++)
arr[i] |= (1 << (temp[j] - 'a'));3. m번 반복하며, 명령어 별로 단어가 몇개 가능한지 확인
이때 아래구문을 호출하는데, 만약 비트 마킹이 1로 되어 있었으면 0으로 바뀌고 0이면 다시 1로 변환되게끔 움직인다.
remember ^= (1 << (b - 'a'));&는 and 연산자라서 둘다 1이어야 1이 됨!
if ( (arr[i] & remember) == arr[i])
result++;
아래는 전체 코드입니다.
#include <iostream>
#include <string>
using namespace std;
int arr[10000] = { 0, };
int n = 0, m = 0;
int remember = 0;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 0; i < 26; i++)
remember |= (1 << i);
string temp;
for (int i = 0; i < n; i++) {
cin >> temp;
for (int j = 0; j < temp.size(); j++)
arr[i] |= (1 << (temp[j] - 'a'));
}
int a;
char b;
while (m--) {
int result = 0;
cin >> a >> b;
remember ^= (1 << (b - 'a'));
for (int i = 0; i < n; i++)
if ( (arr[i] & remember) == arr[i])
result++;
cout << result << "\n";
}
return 0;
}반응형
'알고리즘 > 브루트포스' 카테고리의 다른 글
| [백준] 15684-사다리 조작(C++) (3) | 2020.08.16 |
|---|---|
| [백준] 1038-감소하는 수(C++) (0) | 2020.06.30 |
| [백준] 11502-세 개의 소수 문제(C++) (0) | 2020.03.31 |
| [백준] 1251-단어 나누기(C++) (0) | 2020.03.09 |
| [백준] 1051-숫자 정사각형(C++) (0) | 2020.03.09 |
