JAVA Basic : bitwise AND(비트연산 AND)

스터디사이트 : https://www.hackerrank.com

JAVA Basic : bitwise AND(비트연산 AND)

주어진 숫자배열 (1부터 1씩 증가한 숫자가 요소로 있는 집합. S={1, 2, 3, ... , N} ) 중 두 개의 요소(A, B)를 추출하여,

A와 B의 AND 비트연산을 한 결과가 주어진 숫자보다 작으면서, 그 중에서 가장 큰 숫자를 구하라.

입력

3                ← T : 테스트 케이스들의 갯수. 아래 라인수를 보다시피 3라인, 테스트 케이스도 3.

5 2             ← (테스트케이스1) N K : ⓝ-S 집합의 가장 마지막 요소가 올 수. S={1,2,3,4,5}  ⓚ-AND 비트연산결과의 최대값을 정하는 수

8 5             ← (테스트케이스2) N K

2 2             ← (테스트케이스3) N K

출력

1             ← 테스트케이스1 : 주어진 N, K 의 수 조건에 따라 최대 수를 출력.

4             ← 테스트케이스2 : 주어진 N, K 의 수 조건에 따라 최대 수를 출력.

0             ← 테스트케이스3 : 주어진 N, K 의 수 조건에 따라 최대 수를 출력.

※ 조건

1 <= T <= 10^3

2 <= N <= 10^3

2 <= K <= N

이건 2진수 AND 연산이였다..

단순 10진수의 AND 연산인 줄 알고

왜 1과 2를 곱했는데 0이 나오고 1과 3을 곱했는데 1이 나올까... 많이 고민했었다..

역시 언어는 언어.. 자주 써야 2진수라는 걸 바로 알텐데..ㅋ

  시범 예

N=5, K=2 ▷▶ S={1,2,3,4,5}

1.	A=1, B=2 ▷▶ A&B = 0	A    = 001  B    = 010  A&B =000
2.	A=1, B=3 ▷▶ A&B = 1	A    = 001  B    = 011  A&B =001
3.	A=1, B=4 ▷▶ A&B = 0	A    = 001  B    = 100  A&B =000
4.	A=1, B=5 ▷▶ A&B = 1	A    = 001  B    = 101  A&B =001
5.	A=2, B=3 ▷▶ A&B = 2	A    = 010  B    = 011  A&B =010
6.	A=2, B=4 ▷▶ A&B = 0	A    = 010  B    = 100  A&B =000
7.	A=2, B=5 ▷▶ A&B = 0	A    = 010  B    = 101  A&B =000
8.	A=3, B=4 ▷▶ A&B = 0	A    = 011  B    = 100  A&B =000
9.	A=3, B=5 ▷▶ A&B = 1	A    = 011  B    = 101  A&B =001
10.	A=4, B=5 ▷▶ A&B = 4	A    = 100  B    = 101  A&B =100

10진수를 2진수로 변환하기

이전에 포스팅 해 놓은게 있다.. 오랜만에 보네? ㅋ

http://geoseong.tistory.com/14

오랜만에 2진수 변환하다보면 헷갈리는 소인수분해(?) 원리..

디버깅 1

public static void main(String[] args) { Scanner scan = new Scanner(System.in); int repeat = scan.nextInt(); int temp = repeat; while(repeat-->0){ System.out.println("[repeat " + (temp-repeat) + "]"); int n=scan.nextInt(); int k=scan.nextInt(); int[] s = new int[n]; for(int i=0; i<s.length; i++){ s[i] = i+1; System.out.println("S["+i+"] : " + s[i]); } } }

결과 :  [repeat 1] S[0] : 1 S[1] : 2 S[2] : 3 S[3] : 4 S[4] : 5 [repeat 2] S[0] : 1 S[1] : 2 S[2] : 3 S[3] : 4 S[4] : 5 S[5] : 6 S[6] : 7 S[7] : 8 [repeat 3] S[0] : 1 S[1] : 2

▷ Feedback : 가볍게 T 와 N 을 이용해서 숫자집합인 S에 숫자를 집어넣어봤다. temp변수는 단지 디버깅을 하기위해 정의했으므로 무시해도 된다. 이제 10진수를 2진수로 변환을 하는 코딩을 하면서 A와 B를 추출해야된다.

디버깅 2

public static void main(String[] args) { Scanner scan = new Scanner(System.in); int repeat = scan.nextInt(); int temp = repeat; while(repeat-->0){ System.out.println("[repeat " + (temp-repeat) + "]"); int n=scan.nextInt(); int k=scan.nextInt(); int[] s = new int[n]; // S배열에 N 자리만큼의 숫자를 집어넣는 모습 for(int i=0; i<s.length; i++){ s[i] = i+1; System.out.println("S["+i+"] : " + s[i]); } //end for i // A와 B를 뽑아보쟈; for(int a=1; a<=s.length; a++){ for(int b=a+1; b<=s.length; b++){ System.out.printf("a : %d, b : %d / ", a, b); } System.out.println(); } //end for a, b } //end while }

결과 :  [repeat 1] S[0] : 1 S[1] : 2 S[2] : 3 S[3] : 4 S[4] : 5 a : 1, b : 2 / a : 1, b : 3 / a : 1, b : 4 / a : 1, b : 5 /  a : 2, b : 3 / a : 2, b : 4 / a : 2, b : 5 /  a : 3, b : 4 / a : 3, b : 5 /  a : 4, b : 5 /  [repeat 2] S[0] : 1 S[1] : 2 S[2] : 3 S[3] : 4 S[4] : 5 S[5] : 6 S[6] : 7 S[7] : 8 a : 1, b : 2 / a : 1, b : 3 / a : 1, b : 4 / a : 1, b : 5 / a : 1, b : 6 / a : 1, b : 7 / a : 1, b : 8 /  a : 2, b : 3 / a : 2, b : 4 / a : 2, b : 5 / a : 2, b : 6 / a : 2, b : 7 / a : 2, b : 8 /  a : 3, b : 4 / a : 3, b : 5 / a : 3, b : 6 / a : 3, b : 7 / a : 3, b : 8 /  a : 4, b : 5 / a : 4, b : 6 / a : 4, b : 7 / a : 4, b : 8 /  a : 5, b : 6 / a : 5, b : 7 / a : 5, b : 8 /  a : 6, b : 7 / a : 6, b : 8 /  a : 7, b : 8 /  [repeat 3] S[0] : 1 S[1] : 2 a : 1, b : 2 /

▷ Feedback : S 배열에서 A와 B를 추출하되, A < B 의 공식을 충족하는 코딩을 했다. 이 코딩을 하면서 몇달전에 시험 본 정보처리기사의 알고리즘에서 반복문을 두번 하는 것이 떠올랐다.ㅋ

디버깅 3

public static void main(String[] args) { Scanner scan = new Scanner(System.in); int repeat = scan.nextInt(); int temp = repeat; while(repeat-->0){ System.out.println("[repeat " + (temp-repeat) + "]"); int n=scan.nextInt(); int k=scan.nextInt(); int[] s = new int[n]; // S배열에 N 자리만큼의 숫자를 집어넣는 모습 for(int i=0; i<s.length; i++){ s[i] = i+1; System.out.println("S["+i+"] : " + s[i]); } //end for i // A와 B를 뽑아보쟈; for(int a=1; a<=s.length; a++){ for(int b=a+1; b<=s.length; b++){ System.out.printf("a : %d, b : %d / ", a, b); // A를 2진수로 변환 int calca = a; int mok = calca/2; int rest; String binary=""; while(mok!=0){ rest = calca-(mok*2); System.out.println("\n\ta의 몫 : " + mok + ", a의 나머지 : " + rest); calca=mok; mok=mok/2; binary=rest+binary; } rest = calca-(mok*2); binary=rest+binary; System.out.println("\tbinary - " + binary); } System.out.println(); } //end for a, b } //end while }

결과 :  [repeat 1] S[0] : 1 S[1] : 2 S[2] : 3 S[3] : 4 S[4] : 5 a : 1, b : 2 / binary - 1 a : 1, b : 3 / binary - 1 a : 1, b : 4 / binary - 1 a : 1, b : 5 / binary - 1 a : 2, b : 3 /  a의 몫 : 1, a의 나머지 : 0 binary - 10 a : 2, b : 4 /  a의 몫 : 1, a의 나머지 : 0 binary - 10 a : 2, b : 5 /  a의 몫 : 1, a의 나머지 : 0 binary - 10 a : 3, b : 4 /  a의 몫 : 1, a의 나머지 : 1 binary - 11 a : 3, b : 5 /  a의 몫 : 1, a의 나머지 : 1 binary - 11 a : 4, b : 5 /  a의 몫 : 2, a의 나머지 : 0 a의 몫 : 1, a의 나머지 : 0 binary - 100

▷ Feedback : 여기까지는 a만 2진수로 변환하는 과정을 코딩해봤다.. 그런데 binary라는 변수가 String으로 놓으면 안된다는 것을 깨달았다. 왜냐하면 완성된 2진수가 String 변수면, AND계산할 때 String끼리 어떻게 계산하나?? ㅋ AND연산이니까 각 자릿수가 0 아니면 1이 서로 맞으면 1이고 아니면 0이기 때문에 String[] 배열에다가 2진수 숫자 하나씩 넣고 비교하는게 맞는거같기도 하다.

머릿속에 정리가 잘 안되어서 엑셀에다가 본격적인 디버깅을 돌려보았다..

그러니까 코딩들을 그나마 간소화 시킬 수 있게 되었다!! 

① 차라리 A와 B를 동시에 진행하다가 A의 나머지와 B의 나머지를 곱한 결과를 스택에 넣는다.

② 10진수로 변환을 해야..

다시 pop()하면 일의자리수부터 2진수가 나오는데, 그 수에다가 2^0, 2^1 순차적으로 곱한 후 합한다.

③ 이 합한 10진수가 지정한 K보다 크냐?

크다면 {

목록변수에다가 넣는다.

④ 그리고 그 목록들 중 제일 큰 수를 찾기

0번지를 제일큰놈으로 지정하고

순차적으로 번지수를 찾아가 0번지보다 큰놈이면 그놈이 큰놈으로 바뀌고

마지막 번지수까지 찾아가서 남아있는 큰놈이 젤 큰놈이다

}

디버깅 4

public static void main(String[] args) { Scanner scan = new Scanner(System.in); int repeat = scan.nextInt(); int temp = repeat; while(repeat-->0){ System.out.println("[repeat " + (temp-repeat) + "]"); int n=scan.nextInt(); int k=scan.nextInt(); int[] s = new int[n]; /* S배열에 N 자리만큼의 숫자를 집어넣는 모습 for(int i=0; i<s.length; i++){ s[i] = i+1; System.out.println("S["+i+"] : " + s[i]); } */ // A와 B를 뽑아보쟈; for(int a=1; a<=n; a++){ for(int b=a+1; b<=n; b++){ System.out.printf("a : %d, b : %d / \n", a, b); // A, B를 2진수로 변환 후 AND연산 int temp_a = a; int temp_b = b; LinkedList<Integer> stack = new LinkedList<Integer>(); /* ① AND비트연산 */ while(temp_a!=0 || temp_b!=0){ // A int mok_a = temp_a/2; int rest_a = temp_a-(mok_a*2); System.out.println("\tA의 몫 : " + mok_a + ", A의 나머지 : " + rest_a); temp_a=mok_a; // B int mok_b = temp_b/2; int rest_b = temp_b-(mok_b*2); System.out.println("\tB의 몫 : " + mok_b + ", B의 나머지 : " + rest_b); temp_b=mok_b; stack.push(rest_a*rest_b); // A나머지 , B나머지의 AND비트연산 } //end while // ② AND연산 값을 10진수로 변환하기 int stacksize = stack.size(); // 2의 stacksize 승부터 1씩 줄여갈 거임. int sum; // 2진수 각 자릿수의 10진수 변환값 int total=0; // 2진수의 총합계 while(stacksize-->0){ int num = stack.pop(); //0 아니면 1이겠지. System.out.println("num은 : " + num + "\nstacksize : " + stacksize); int times=1; //2의 0승 for(int i=0; i<stacksize; i++){ times=times*2; //i=1 , times=1*2 / i=2, times=2*2 / i=3, times=2*2*2 } sum = num * times; System.out.println(stacksize + "번째 자리의 10진수 :" + sum); total = total + sum; System.out.println("현재까지의 총합 : " + total + "\n--------------"); } System.out.printf("\ta : %d, b : %d의 total : %d\n------------------------------\n", a, b, total); } //end for b System.out.println(); } //end for a, b } //end while } // end main

결과 :  [repeat 1] a : 1, b : 2 /  A의 몫 : 0, A의 나머지 : 1 B의 몫 : 1, B의 나머지 : 0 A의 몫 : 0, A의 나머지 : 0 B의 몫 : 0, B의 나머지 : 1 num은 : 0 stacksize : 1 1번째 자리의 10진수 :0 현재까지의 총합 : 0 -------------- num은 : 0 stacksize : 0 0번째 자리의 10진수 :0 현재까지의 총합 : 0 -------------- a : 1, b : 2의 total : 0 ------------------------------ a : 1, b : 3 /  A의 몫 : 0, A의 나머지 : 1 B의 몫 : 1, B의 나머지 : 1 A의 몫 : 0, A의 나머지 : 0 B의 몫 : 0, B의 나머지 : 1 num은 : 0 stacksize : 1 1번째 자리의 10진수 :0 현재까지의 총합 : 0 -------------- num은 : 1 stacksize : 0 0번째 자리의 10진수 :1 현재까지의 총합 : 1 -------------- a : 1, b : 3의 total : 1 ------------------------------

▷ Feedback : 디버깅을 하면서 깨달은 ①번과 ②번과정까지 했다.  으아 매우 오래걸렸따 ㅋㅋ 문제는 쉬워보였지만 여러 기술들의 집합이다.. 스택을 썼고, 10진수를 2진수로 변환하고, AND연산 한 2진수를 10진수로 다시 변환했다.. 이제 ArrayList나 다시 LinkedList같은곳에 AND연산 결과 10진수값을 집어넣고 비교하는 일이 남았다. 아! 그런데 생각해보니 꼭 ③, ④번 처럼 ArrayList를 만들어서 반복해갖고 한자리씩 검사할 필요가 없다. 왜냐하면 반복을 하면서 하나씩 A&B에 대한 total값이 생기므로, 새로운 저장공간을 만들어서 total값을 임시로 저장시킨다. 그리고 다음 반복문을 돌려서 나온 A&B에 대한 total값과 새로운 저장공간(이전 반복문으로 나온 total값)을 비교해서, 가장 큰 값을 구하는데, 주어진 K값보다 작으면 출력시키면 된다.. ㅋ 아래는 전체적인 코딩에 대한 반복문과 조건문을 간략히 정리해봤다.

디버깅5

public static void main(String[] args) { Scanner scan = new Scanner(System.in); int repeat = scan.nextInt(); int temp = repeat; List<Integer> maximum = new ArrayList<Integer>(); /* T(repeat) : 만큼 반복 */ while(repeat-->0){ System.out.println("[repeat " + (temp-repeat) + "]"); int n=scan.nextInt(); int k=scan.nextInt(); //int[] s = new int[n]; int total_max=0; /*// S배열에 N 자리만큼의 숫자를 집어넣는 모습 for(int i=0; i<s.length; i++){ s[i] = i+1; System.out.println("S["+i+"] : " + s[i]); } //end for i*/ // A와 B를 뽑아보쟈; for(int a=1; a<=n; a++){ for(int b=a+1; b<=n; b++){ System.out.printf("a : %d, b : %d / \n", a, b); // A, B를 2진수로 변환 후 AND연산 int temp_a = a; int temp_b = b; LinkedList<Integer> stack = new LinkedList<Integer>(); /* ① AND비트연산 */ while(temp_a!=0 || temp_b!=0){ // A int mok_a = temp_a/2; int rest_a = temp_a-(mok_a*2); //System.out.println("\tA의 몫 : " + mok_a + ", A의 나머지 : " + rest_a); temp_a=mok_a; // B int mok_b = temp_b/2; int rest_b = temp_b-(mok_b*2); //System.out.println("\tB의 몫 : " + mok_b + ", B의 나머지 : " + rest_b); temp_b=mok_b; stack.push(rest_a*rest_b); // A나머지 , B나머지의 AND비트연산 } //end while // AND연산 값을 10진수로 변환하기 int stacksize = stack.size(); // 2의 stacksize 승부터 1씩 줄여갈 거임. int sum; // 2진수 각 자릿수의 10진수 변환값 int total=0; // 2진수의 총합계 while(stacksize-->0){ int num = stack.pop(); //0 아니면 1이겠지. //System.out.println("num은 : " + num + "\nstacksize : " + stacksize); int times=1; //2의 0승 for(int i=0; i<stacksize; i++){ times=times*2; //i=1 , times=1*2 / i=2, times=2*2 / i=3, times=2*2*2 } sum = num * times; //System.out.println(stacksize + "번째 자리의 10진수 :" + sum); total = total + sum; //System.out.println("현재까지의 총합 : " + total + "\n--------------"); } //end while stacksize System.out.printf("\tk : %d, a : %d, b : %d의 total : %d\n------------------------------\n", k, a, b, total); // 반복 될때마다 total이 새로 나오니까 새로운 변수 total_max에다가 total값을 집어넣는다. // 그 이후 total_max와 total과 비교 해서 total이 total_max보다 크면 그 total은 total_max로 승급. if( total < k && total_max < total ){ total_max = total; System.out.println("이제 total_max는 total의 수이다. total_max : " + total_max); } } //end for b System.out.println(); } //end for a System.out.println("해당 케이스의 total_max는 : " + total_max); } //end while T(repeat) } // end main

결과 :  [repeat 1] a : 1, b : 2 /  k : 2, a : 1, b : 2의 total : 0 ------------------------------ a : 1, b : 3 /  k : 2, a : 1, b : 3의 total : 1 ------------------------------ 이제 total_max는 total의 수이다. total_max : 1 a : 1, b : 4 /  k : 2, a : 1, b : 4의 total : 0 ------------------------------ a : 1, b : 5 /  k : 2, a : 1, b : 5의 total : 1 ------------------------------ a : 2, b : 3 /  k : 2, a : 2, b : 3의 total : 2 ------------------------------ a : 2, b : 4 /  k : 2, a : 2, b : 4의 total : 0 ------------------------------ a : 2, b : 5 /  k : 2, a : 2, b : 5의 total : 0 ------------------------------ a : 3, b : 4 /  k : 2, a : 3, b : 4의 total : 0 ------------------------------ a : 3, b : 5 /  k : 2, a : 3, b : 5의 total : 1 ------------------------------ a : 4, b : 5 /  k : 2, a : 4, b : 5의 total : 4 ------------------------------ 해당 케이스의 total_max는 : 1 [repeat 2] ...

▷ Feedback : 이제 디버깅 주석을 빼고 해보자..

디버깅6

public static void main(String[] args) { Scanner scan = new Scanner(System.in); int repeat = scan.nextInt(); int temp = repeat; List<Integer> maximum = new ArrayList<Integer>(); /* T(repeat) : 만큼 반복 */ while(repeat-->0){ int n=scan.nextInt(); int k=scan.nextInt(); int total_max=0; // A와 B를 뽑아보쟈; for(int a=1; a<=n; a++){ for(int b=a+1; b<=n; b++){ // A, B를 2진수로 변환 후 AND연산 int temp_a = a; int temp_b = b; LinkedList<Integer> stack = new LinkedList<Integer>(); /* ① AND비트연산 */ while(temp_a!=0 || temp_b!=0){ // A int mok_a = temp_a/2; int rest_a = temp_a-(mok_a*2); temp_a=mok_a; // B int mok_b = temp_b/2; int rest_b = temp_b-(mok_b*2); temp_b=mok_b; stack.push(rest_a*rest_b); // A나머지 , B나머지의 AND비트연산 } //end while // AND연산 값을 10진수로 변환하기 int stacksize = stack.size(); // 2의 stacksize 승부터 1씩 줄여갈 거임. int sum; // 2진수 각 자릿수의 10진수 변환값 int total=0; // 2진수의 총합계 while(stacksize-->0){ int num = stack.pop(); //0 아니면 1이겠지. int times=1; //2의 0승 for(int i=0; i<stacksize; i++){ times=times*2; //i=1 , times=1*2 / i=2, times=2*2 / i=3, times=2*2*2 } sum = num * times; total = total + sum; } //end while stacksize // 반복 될때마다 total이 새로 나오니까 새로운 변수 total_max에다가 total값을 집어넣는다. // 그 이후 total_max와 total과 비교 해서 total이 total_max보다 크면 그 total은 total_max로 승급. if( total < k && total_max < total ){ total_max = total; } } //end for b } //end for a System.out.println(total_max); } //end while T(repeat) } // end main

결과 :  1 4 0

▷ Feedback : 그런데.. 다른 케이스를 입력하고 돌려보면 TimeOut이 뜬다. 162줄의 케이스는 잘되는데.. 176줄의 케이스는 TimeOut이다.. 그러던 중.. 다른 사람이 한 놀라운 코딩을 발견했다.

결과1

public static void main(String[] args) { Scanner in = new Scanner(System.in); int t = in.nextInt(); for(int a0 = 0; a0 < t; a0++){ int n = in.nextInt(); int k = in.nextInt(); int finalResult = 0; for(int i = 1; i < n ; i++){ for(int j = i+1; j <= n ; j++){ int amp = i&j; if(amp < k && amp > finalResult) finalResult = amp; } } System.out.println(finalResult); } }

결과 :  1 4 0

▷ Feedback : 2진수를 10진수로, 10진수를 2진수로 변환하지 않아도 저렇게 할수있다.. 나는 바보였돠...

결과2

public static void main(String[] args) { Scanner in = new Scanner(System.in); int t = in.nextInt(); for(int a0 = 0; a0 < t; a0++){ int n = in.nextInt(); int k = in.nextInt(); if(((k-1)|k) > n && k%2==0){ System.out.println(k-2); }else{ System.out.println(k-1); } } }

결과 :  1 4 0

▷ Feedback : 나머지, 몫, total_max 등을 구하기 위한 반복문이 다 배제되었다.. 무슨 원리로 저렇게 한 건지 잘 이해가 안간다.. k%2=0이면 짝수, k%2=1이면 홀수가 된다... ※ 조건 1 <= T <= 10^3 2 <= N <= 10^3 2 <= K <= N k가 홀수이고, k-1이 짝수라면.. 11의 2진수 :  k = 1011 10의 2진수 :  k-1 = 1010 11과 10의 2진수 | (or) 연산 1011 (or) 1010 k = 1011 ※ ( (k-1) | k ) = k 11과 10의 2진수 & (and) 연산 1011 (and) 1010 k-1 = 1010 ※ ( (k-1) & k ) = k-1 위의 조건에 따라 적용하면, ( (k-1) | k ) <= n 도 true라는 것을 알 수 있다. k가 짝수이고, k-1이 홀수라면.. 그리고 ( (k-1) | k ) <= n 이 TRUE 이면 k-1 이 된다....  음... 아래는 설명의 원본이다. 근데 읽어도 당최 이해가안된다.. 이해가시면 누가 설명좀해주세요.. ㅋ