Baekjoon 5568 카드 놓기 - 비트 마스킹 & 재귀

5568번: 카드 놓기

카드 n이 10이하이고 k도 4이하여서 비트마스킹과 재귀를 사용하기로 했다.

1. 카드를 numbers 배열에 넣는다.👨‍🏫

int[] numbers = new int[N + 1];
for (int i = 1; i <= N; i++) {
  numbers[i] = Integer.parseInt(br.readLine());
}

비트마스킹을 하기 위해 인덱스는 1부터 시작한다.

2. 반복문을 통해 카드를 선택한다.

for (int i = 1; i <= N; i++) {
  Possibility(numbers, String.valueOf(numbers[i]), 1 << i, 1);
}

1 << i : i번째 카드를 뽑았으므로 bit 매개변수를 i번 쉬프트 해준다.

3. Possibility 메서드🔹

private static void Possibility(int[] numbers, String number, int bit, int count) {
  if (count == k) {
    hs.add(Integer.parseInt(number));
  }
  for(int i =1;i<=N;i++){
    if((bit & (1 << i)) > 0){
      continue;
    }
    Possibility(numbers, number + String.valueOf(numbers[i]), bit | (1 << i), count+1);
  }
}

카드 뽑은 횟수가 k번 된다면 HashSet hs에 number를 넣어준다.

3-1. & 연산자

Possibility 메서드에서 &를 쓰는 코드를 주목해보자.

if((bit & (1 << i)) > 0)

✅ 매개변수 bit를 비트연산 &를 사용하여 i번째 카드가 이미 사용한지 체크해준다.

✅ 만약 사용된 카드라면 continue로 넘어가준다.

3-2. | 연산자

Possibility 메서드에서 &를 쓰는 코드를 주목해보자.

Possibility(numbers, number + String.valueOf(numbers[i]), bit | (1 << i), count+1);

✅ 매개변수 bit를 비트연산 &를 사용하여 i번째 카드를 사용했음을 알리기 위해 바꿔준다.

---

🔔비트마스킹 쓸 때 주의할 점

1. 범위 ❗

• 비트마스크는 쉬프트연산자를 쓰기 때문에 범위를 벗어날 수 있는 문제에는 쓸 수 없다.

2. just 도구 ❗

• 비트마스크는 문제를 원활하게 풀어주는 도구일 뿐이다.

3. 연산자 우선순위 ❗

• 비트 연산자는 연산자 우선순위가 낮기 때문에 괄호를 꼭 써줘야 한다.