코딩 공부/백준

[백준][C++] 18119 단어 암기

김 정 환 2021. 4. 20. 13:19
반응형

www.acmicpc.net/problem/18119

 

18119번: 단어 암기

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

www.acmicpc.net

 

 

 

알고리즘 종류

구현

문자열

 

 

사고 과정

비트마스크를 사용하지 않고 구현하면 제출이 되었지만, 시간이 오래 걸렸습니다. 비트마스크를 사용하면 어떤 알파벳이 있는지 쉽게 알 수 있습니다.

 

1. 처음에는 모든 알파벳을 기억한다고 했으니 or 연산으로 모든 알파벳을 기억합니다.

 

2. 단어를 입력받으면, dict 배열에서 단어의 문자를 or 연산으로 기억합니다.

 

3. 쿼리르 입력 받으면, And와 or 연산을 이용해서 잊어버리거나 기억을 합니다. 그리고 현재 기억하고 있는 알바벳들(remember)와 단어의 문자들이 저장된 dict을 And로 비교해서 모두 읽을 수 있는지 확인합니다.

 

 

 

구현(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <string>
 
using namespace std;
 
int n, m;
int remember = 0;
 
int dict[10001];
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    
    cin >> n >> m;
    
    // or 연산으로 모든 알파벳을 기억합니다. 
    for (int i = 0; i < 26; i++) {
        remember |= (1 << i);
    }
    
    string str;
    for (int i = 0; i < n; i++) { // bring a word
        cin >> str;
 
        for (int j = 0; j < str.size(); j++) { // 단어의 알파벳을 or 연산으로 저장합니다. 
            char c = str[j]; 
            dict[i] |= (1 << (c-'a'));
        }
    }
 
    int o;
    char x;
    for (int i = 0; i < m; i++) {
        int cnt = 0;
        cin >> o >> x;
 
        if(o==1) remember &= ~(1 << (x -'a')); // ~ 으로 반전시켜주고 &으로 제외시켜줍니다. 
        else remember |= (1 << (x -'a')); // or 연산으로 더해줍니다. 
 
        for (int j = 0; j < n; j++) {
            if ((dict[j] & remember) == dict[j]) // dict에 있는 단어의 알파벳과 현재 기억하고 있는 알파벳들을 비교합니다. 
               cnt++;
        }
        cout << cnt << "\n";
    }
}
cs

 

 

 

시행착오

반응형

'코딩 공부 > 백준' 카테고리의 다른 글

[백준][C++] 1918 후위 표기식  (0) 2021.04.20
[백준][C++] 9081 단어 맞추기  (0) 2021.04.20
[백준][C++] 1062 가르침  (0) 2021.04.19
[백준][C++] 1941 소문난 칠공주  (0) 2021.04.19
[백준][C++] 3687 성냥개비  (0) 2021.04.19