김지민은 학생들에게 K개의 글자를 가르칠 수 있고, 가르치고 난 후 학생들은 그 K개의 글자로만 이루어진 단어만을 읽을 수 있다.
남극언어의 모든 단어는 "anta"로 시작되고, "tica"로 끝난다. 남극언어에 단어는 N개 밖에 없다고 가정한다. 학생들이 읽을 수 있는 단어의 최댓값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문자로만 이루어져 있고, 길이가 8보다 크거나 같고, 15보다 작거나 같다. 모든 단어는 중복되지 않는다.
출력
첫째 줄에 김지민이 K개의 글자를 가르칠 때, 학생들이 읽을 수 있는 단어 개수의 최댓값을 출력한다.
🍀 풀이
2^26은 int형 범위 안에 있기 때문에'학생들이 배운 알파벳'을 비트화하였다.
알파벳의 순서를 자릿수처럼 생각하며left shift 연산(`1<<n`)을 활용했다.
e.g. c를 비트화 1을 왼쪽으로 2('c' - 'a')만큼 비트 이동한다. 100(bit) = 4(십진수)
학생들이 배우는 알파벳이 여러개인 경우 OR 비트연산(`|`)을 활용했다.
e.g. 학생들이 a와 c를 배운 경우 1(bit) | 100(bit) = 101(bit) = 5(십진수)
같은 방법으로 남극 언어의 단어마다 알파벳들을 비트화해서 저장했다.
비트 수를 체크하여 `K`개의 알파벳을 배웠는 지 확인했다.
`K`개의 알파벳을 배웠다면, 남극 언어의 단어들을 순차적으로 확인하며 배운 알파벳으로 읽을 수 있는 단어인지 확인했다.
이때는 AND 비트연산(`&`)을 활용했다.
배운 언어와 남극 언어의 단어를 AND 비트연산하면 공통된 부분이 추출된다.
공통된 부분이 남극 언어의 단어와 같은 경우, 배운 알파벳으로 해당 단어를 읽을 수 있다는 뜻이다.
e.g. 'antancttica' 배운 언어와 남극 언어의 단어를 AND 비트연산한 결과가 남극 언어의 단어와 일치한다. 학생들은 해당 단어를 읽을 수 있다.
e.g. `antabndtica' 배운 언어와 남극 언어의 단어를 AND 비트연산한 결과가 남극 언어의 단어와 불일치한다. 학생들은 해당 단어를 읽을 수 없다.
1. `fixedBit`: [a, n, t, i, c]은 필수로 배워야하는 알파벳이므로 미리 비트로 만들어 저장한다. 2. 남극 언어의 단어들을 순차적으로 입력받는다. 단어별로 포함된 알파벳을 모두 OR 비트연산한 후 `wordsBit`에 저장한다. 3. 부분집합을 활용하여 알파벳을 배우는 함수 `checkedAlphabet`을 호출한다. 1. `index`: 현재 배울 예정인 알파벳의 순서를 저장한다. (`a`= 0, `b`= 1, ... ) 2. `currentBit`: 학생들이 배운 알파벳들을 OR 비트연산한 결과를 저장한다. 4. 학생들이 배운 알파벳 개수가 `K`개인 경우 1. 남극 언어의 단어들을 순차적으로 확인하며 학생들이 배운 알파벳으로 만들 수 있는 단어인지 확인한다. 맞다면 `wordCount`를 1 더한다. 2. `wordCount`가 `max`보다 크다면 `max`값을 갱신한다. 3. 함수를 종료한다. 5. 모든 알파벳을 확인했다면 함수를 종료한다. 6. `currentBit`에 포함되지 않은 알파벳이라면 포함시킨 후 `checkedAlphabet`를 재귀호출한다. ([a, n, t, i, c] 때문에 조건이 붙는다) 7. 현재 알파벳을 포함시키지 않고, `checkedAlphabet`를 재귀호출한다. 8. `checkedAlphabet`가 모두 종료되면 `max`를 출력한다.
💻 전체 코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
static int K, max, fixedBit;
static int[] wordsBit;
public static void main(String[] args) throws Exception {
init();
checkedAlphabet(0, fixedBit);
System.out.println(max);
}
static void init() throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String input = br.readLine();
int N = Integer.parseInt(input.substring(0, input.indexOf(' ')));
K = Integer.parseInt(input.substring(input.indexOf(' ') + 1));
max = 0;
fixedBit = (1 << ('a' - 'a')) | (1 << ('n' - 'a')) | (1 << ('t' - 'a')) | (1 << ('i' - 'a')) | (1 << ('c' - 'a'));
wordsBit = new int[N];
for (int n = 0; n < N; n++) {
input = br.readLine();
int bit = fixedBit;
for (int i = 4; i < input.length() - 4; i++) {
bit |= (1 << (input.charAt(i) - 'a'));
}
wordsBit[n] = bit;
}
}
static void checkedAlphabet(int index, int currentBit) {
if (Integer.bitCount(currentBit) == K) {
int wordCount = 0;
for (int wordBit : wordsBit) {
if ((currentBit & wordBit) == wordBit) {
wordCount++;
}
}
if (max < wordCount) max = wordCount;
return;
}
if (index == 26) return;
if ((currentBit & (1 << index)) == 0) checkedAlphabet(index + 1, currentBit | (1 << index));
checkedAlphabet(index + 1, currentBit);
}
}
💫 리뷰
10개월 전에 도전했다가 실패했던 문제! 나.. 성장했다!!! ๑•̀∀•́ฅ
비트마스킹은 문제를 보고 비트마스킹으로 풀어야 겠다는 생각이 바로 안나서 어렵지만, 비트마스킹 문제라는것을 알고 풀이를 고민하는 과정은 재밌다.ㅎㅎ
