[백준 2830번] 행성X3 (자바)

힌트 문제 중 하나로 현재도 나를 괴롭히고 있는 이진법 행성사람들
해체 한 번 해보자고,

 

 

 

 

 

행성X3 문제 - https://www.acmicpc.net/problem/2830

2830번: 행성 X3

 

---

 

처음 문제를 읽었을 때

 

1. 입력되는 자연수를 10진법 → 2진법으로 변경한다.

2. XOR연산을 한다.

3. 값을 다시 10진법으로 바꾼다.

 

어?

너무 쉬운거 아닌가? 

라는 착각을 했다.

 

착각을 품고 어떻게 해야할 지 끄쩍이기 시작했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int[] numArr = new int[N];
        int[] binaryArr =new int[N];
        String F;
        int result =0;
        int num1 =0;
        int num2 =0;
        for (int i = 0; i < N ; i++) {
            numArr[i] = Integer.parseInt(br.readLine());
            binaryArr[i] = Integer.parseInt(Integer.toBinaryString(numArr[i]));
        }


        for (int i = 0; i < N-1 ; i++) {
            for (int j = i+1; j < N ; j++) {
                num1=binaryArr[i];
                num2=binaryArr[j];
                F=String.valueOf(num1^num2);
                result=Integer.parseInt(F, 2);
                result+=result;

            }
        }

        System.out.println(result);
    }
}

 

 

결과는 실패.

 

시간은 둘째 문제고

 

나름 기대하고 코드를 짰는데

마지막 예제에서 오류가 떠버렸다.

시간을 널널하게 줘도 맞출수가 없는거다

 

왜 마지막 예제만 에러가 뜨는지 

디버깅을 돌렸는데

갑자기 1956이 나온다고.....?

 

뭐가 문제인지 다시 해당 수를 직접 잡고해도 1956이 나온다

머리쥐난다.

 

나중에 찾아봤는데

저게 성공했어도 이중for문이라 시간복잡도에서 걸려서 실패라고 한다.

아이디어가 도저히 떠오르지 않아서 

다른 사람 코드를 분석하기로했다.

---

 

https://developer-rabbit.tistory.com/entry/%EB%B0%B1%EC%A4%80-2830%EB%B2%88Java%EB%B9%84%ED%8A%B8%EC%97%B0%EC%82%B0%EC%9E%90-%ED%96%89%EC%84%B1-X3

[백준 2830번][Java][비트연산자] 행성 X3

 

---

 

https://wooooozin.tistory.com/entry/%EB%B0%B1%EC%A4%80-2830%EB%B2%88-%ED%96%89%EC%84%B1-X3

백준 2830번 - 행성 X3

 

 

---

보통 다른사람의 코드를 보면 속이 펑 하고 뚫리는데

행성 문제는 진짜 

고구마만 일주일 물없이 먹은 것 같은 느낌이였다.

아마 그것은 이진법 공부를 게을리한 나의 탓이겠지만...

사전학습 이진법 공부한날의 느낀점

저렇게 쓰기만하고.... 복습을 안한 결과였다

예견된 에러

과거의 나 반성해야겠다

(이번 포스팅을 계기로 이진법을 잡고가야지!!!!)

여기서 몇 가지를 알고가자면...

---

* XOR연산 : 입력값을 받아 비교했을때 같으면 0, 다르면 1 을 출력하는 것

XOR연산

---

* 2진법표기  : 10진법 N을 2로 몫이 0이 될때까지 나눠주는데

그 단계마다 나오는 1 or 0 의 나머지를 나열한게 N의 2진법표기!

 

10의 2진법표기

 

10 = 1010(2)

 

10진법으로 변화하는 법은 

1 0 1 0 = 10

 

1  *  2^3  +  1  *  2^1  =  10

더 자세히 풀어보면

[ (1  *  2^3) + (0  *  2^2) + (1  *  2^1) + (0  *  2^0) ] =10

---

 

이렇게 계산이 되기 때문에

행성의 친밀도의 합을 구해야하는 나는

각 자리의 1의 갯수를 찾아야한다!

 

각 자리수의 1을 카운팅 하는 법은

배열의 인덱스 = 2^n 자리

해당 인덱스의 값 = 1이 나온 합이다.

 

위에 다른 사람들의 코드를 살펴보면

배열 사이즈를 20으로 잡아 선언한 공통점이 있다.

 

그 이유는

 

거주민의 수  = N

 (1 ≤ N ≤ 1,000,000) 

 

1,000,000 = 1000^2

2^9 < 1000 < 2^10

 

2^9 = 512

" 2^10 = 1024 "

2^11 = 2048

그래도 잘 모르겠으면 1000000을 2로 20번 나누어보길

1000000이 2진법으로 20자리가 나온다

 

 

다시 맨 위에 풀이 코드로 돌아가서

각 자리수(20자리)를 나타낼 수 있는 사이즈가 20인 배열을 선언하고

int[] count = new int [20];

 

for 문으로 numArr[에 들어온 자연수를 하나씩 불러올거다

i = 0 ~ 19까지

numArr[0]~numArr[19]

처음으로 numArr[0]을 부르게 되고

그 자연수를 가지고 반복문 while을 돌려서 

 

while (name > 0) {

count[index++] += name % 2;

자연수(name)를 2로 나눈, 나머지를 카운트 배열에 더해준후

자리수를 변경해줘야 하니 인덱스는 1증가 해준다.

그리고 위에서

2로 나눈 나머지를 배열 넣어줬으니 그에 맞게 자연수(name)를 2로 나눠주는 부분도 구현한다.

 name /= 2;

}

 

이렇게 자연수(name)이 더이상 나눠지지 않을 때까지 반복한다.

그렇게 되면 위에서 설명한

이 예시처럼 이진법표기과정이 구현됐다

예시대로라면  1 0 1 0 이 순서대로 count배열 안에 들어가게 되는것!

 

그 후 다시 한 번 for문을 돌면서 

카운트 배열 각 자리에 있는 1이 나온 횟수를 뽑아준다

 

여기서, 2진법은 1 or 0 이기때문에

n에 1이 나온 횟수를 빼면 0이 나온 횟수를 알 수 있다.

 

for (int i = 19; i >= 0; i--) { sum += (long) count[i] * (n - count[i]);

i 가  19~ 0까지 줄어들면서

 

비트가 다른 부분을 구할예정

count[i] * (n - count[i]) // 1이 나온 횟수  * 0이 나온 횟수

이 부분은 N개의 자연수들의 각자리에서 1이 나온 횟수 0이 나온 횟수를

(1, 0이 나온건 비트가 같지 않기 때문에 XOR연산상 1이 된다는것 그렇게 1이되는 경우의 수를 찾아야함)

곱해 경우의 수를 만드는 것! 

그 후 1이 나오는 경우의 수를 각 2^n에 곱해줘야한다.

이때 자릿수가 커져서 int로는 못 담으니 long에 담길 수 있게 해줘야함! 

 

여기서 내가 막혔던 부분....

 sum <<= 1;

이게 뭐냐 진짜 한참을 서치했다....

우선 비트연산자에   [  <<는 X2   ],   [   >>는 / 2   ] 인데

<< i 를 두면 2^i 라는 것!

따라서 위에 코드는 2^1씩 증가가 되는 것이다.

 

잘 이해가 안된다면 

아래 블로거님 처럼

 

sum += (long)Math.pow(2, i) * count[i] * (n - count[i]); 로

Math.pow(n, m) 은   n^m을 나타냄

 끝내고 바로 sum을 출력해도 좋을 것 같다!

---

---

https://blog.naver.com/jhsfully/223078021804

2830번: 행성 X3

 

이분!!!!!!!! 나의 구세주!!!!!!!!!!!

코드를 다 해체하고나서

알것도 같고, 모르는것도 같은 그런 찝찝한 부분이 있었는데

그 부분을 완전 속 시원히 긁어주심!!!

진짜 상세하고도 상세하게 설명해주셨다!

---

---

 

 

우와

이렇게 첫 코드해체 나름 성공적인데

시간 무슨일?

낼 출근 어떻게....또

그래도 확실히 넘어가니까 속은 후------련.

 

 

복습을 게을리하지말자.

코테에게 큰 코 다침.

 

또보자 이진법!