[백준]#18119 단어 암기
문제
준석이는 영어 단어를 외우려고 한다. 사전에는 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를 잊고 있었음이 보장된다.
출력
각 쿼리마다 정수 하나를 출력한다.
예제 입력 1
5 10
apple
actual
banana
brick
courts
1 l
1 b
1 c
1 n
2 l
2 b
1 s
2 c
2 s
2 n
예제 출력 1
3
1
0
0
1
1
1
3
4
5
풀이
이 문제는 비트마스킹을 이용해서 풀 수 있었다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");
int N = Integer.parseInt(input[0]);
int M = Integer.parseInt(input[1]);
StringBuilder sb = new StringBuilder();
int know = (1<<26)-1; //처음에는 모든 알파벳을 알기 때문에 26자리를 1로 모두 채움
int[] words = new int[N];
for(int i=0; i<N; i++) { //알파벳이 존재하면 해당 자릿수에 1
int binary = 0;
String str = br.readLine();
for(int j=0; j<str.length(); j++) {
char x = str.charAt(j);
int y = (1<<(x-'a')); //0~25 26개의 알파벳, 자리수 만큼 쉬프트 연산
binary |= y;
words[i] = binary;
}
}
for(int i=0; i<M; i++) {
input = br.readLine().split(" ");
int o = Integer.parseInt(input[0]);
int x = input[1].charAt(0) - 'a';
int cnt = N;
if(o==1)
know -= (1<<x); //알파벳을 잊으면 알고있는 2진수에서 해당 자리 0으로 바꿈
else
know += (1<<x); //알파벳을 기억해내면 알고있는 2진수에서 해당 자리 1으로 바꿈
for(int j=0; j<N; j++) {
int word = words[j];
if((word&know) != word) //And 연산 후 숫자가 해당 단어랑 다를 경우 갯수 카운트에서 1씩 빼줌
cnt--;
}
sb.append(cnt).append("\n");
}
System.out.print(sb.toString());
}
}
Author And Source
이 문제에 관하여([백준]#18119 단어 암기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@pss407/백준18119-단어-암기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)