30 Days of Code > Day29:Bitwise AND

마무리 - 30 Days of Code > Day29:Bitwise AND

해커랭크의 tutorials 중 30 Days of Code의 마지막 날이다.

python 공부를 시작하고 30일 동안 큰 어려움 없이 꾸준히 할 수 있었다.

이런 학습 방식이 참 마음에 든다. 작지만 꾸준하게 할 수 있도록 작은 문제들을 부담없는 수준에서 하나씩 제시하고 또 한 문제 이상 풀 수 없도록 24시간마다 한 문제씩 open되는 방식이, 뭐랄까 작은 성공 경험을 느끼고 부담을 줄여서 꾸준히 할 수 있게끔 유도해 준다고 해야하다.

여튼 마지막 문제인 만큼 풀기는 했지만, 좀 더 나은 방법을 찾기위해서는 나름 생각이 필요한 문제여서 정리를 해본다.

(해결 후 discussions를 참고했다)

문제요약

Set S는 {1, 2, 3, ..., N}으로 주어지고, S에 속하는 A와 B(A<B)가 있을 때 A&B의 최댓값을 출력한다. 단 A&B는 주어진 K보다 작아야 한다. (K<=N)

(1<=T<=10^3, 2<=N<=10^3, 2<=K<=N)

Sample Input

3
5 2
8 5
2 2

Sample Output

1

4

0

풀이

처음 내가 풀었던 방식은 K-1과 나머지 원소들과의 &값 중 최댓값을 찾는 거였다. & 연산은 둘 중 작은 값보다 큰 값이 나올 수 없는 특징이 있기 때문에, K보다 작은 최댓값인 K-1과 나머지를 &하면 그 중 최댓값이 들어있을 거라는 생각이었다. 최종적으로 통과는 했으나, 검증이 부족함이 있었다. 그리고 다음 방법을 보게 되었다. 결국 이 방법에 의해 내가 푼 풀이도 정답이 나올 수 있었던 것이나, 실제로는 더 간단하게 풀 수 있는 문제였다.

처음엔 이해가 어려웠으나 정리를 해보면,

K가 홀수인 경우에는 K&(K-1)은 항상 K-1이 된다. 왜냐하면 K-1이 짝수이므로 첫 번째 bit는 0이다. 따라서 K는 K-1에서 첫 번째 bit만 1로 바뀌고 나머지는 같기 때문에 결국 K&(K-1) = K-1이된다.

K가 짝수인 경우에는, 우선 K-1이 홀수이고 K-2가 다시 짝수가 되므로 위와 같은 논리로 K-2는 항상 나올 수 있다. 그러면 K가 짝수인 경우 K-1일 나올 수 있는 경우가 있는지 찾아야한다. 결과적으로 (K|K-1)&K-1 = K-1이 된다. or 연산이므로 K|(K-1)은 K-1의 모든 bit를 포함하고 K-1과 &를 하면 당연히 K-1이 나온다. 그럼 여기서 K|(K-1) <= N라면, K-1이 가능하고 아니면 K-2가 답이된다. 물론 K보다 큰 값을 선택해서 동일하게 나올 수 있지만 (K+0,1,...)|(K-1)이 가장 작은 경우가 K일 때이므로 K만 확인하면 된다.