첫 골드 3 문제이다 좀 두려움이 앞섰지만 그래도 풀어보려고 노력해보겠다..
문제는 어렵지 않다
그냥 XOR 연산 처리한걸 다 합하면 된다 하지만 그냥 풀게 되면 시간 초과가 난다
package G3_Baekjoon;
import java.util.Scanner;
public class Baekjoon2830 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int[] X3 = new int[N];
int answer = 0;
for (int i = 0; i < N; i++) {
X3[i] = sc.nextInt();
}
for (int i = 0; i < X3.length - 1; i++) {
for (int j = i + 1; j < X3.length; j++) {
answer += X3[i] ^ X3[j];
}
}
System.out.println(answer);
}
}처음에 풀은 방식이다 경우의 수에 대해 모두 더해주는 코드를 짜고 좀 의심스럽게 제출해봤다 역시 시간초과가 난다
package G3_Baekjoon;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Baekjoon2830 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int[] X3 = new int[N];
int answer = 0;
for(int i = 0; i < N; i++){
X3[i] = Integer.parseInt(br.readLine());
}
for(int i = 0; i < X3.length -1; i++){
for(int j = i+1; j < X3.length; j++){
answer += X3[i] ^ X3[j];
}
}
System.out.println(answer);
}
}두번째는 BufferedReader를 사용해봤다 역시 시간 초과가 난다. 이러면 시간을 줄일 수 있는 방법을 고민해봐야겠다
고심에 고심을 진행중
이 부분에서 힌트를 얻은 것 같다
7의 비트연산자는 111
3의 비트연산자는 011
5의 비트연산자는 101
3번째 자리 1 / 0 / 1 은 1이 2개 들어가는데 그럼 결국 두번 계산한다는 뜻이다 그럼 세번째는 4니깐 4 * 2 = 8
2번째 자리 1 / 1 / 0 도 1이 2개 그럼 1 / 1 을 제외한 두번 계산한다는 뜻이다. 그럼 두번째는 2 니깐 2 * 2 = 4
1번째 자리는 1 / 1 / 1 로 어떤거랑 계산해도 0이 나오게 된다.
그럼 받는 숫자를 비트연산자로 바꿔서 배열에 자릿수에 1과 0이 몇번 들어가는지 알게 되면 빠르게 풀 수 있을 것 같다.
이게 확실한지
예제 3번으로 테스트해보자
9 = 1001
13 = 1101
1 = 0001
9 = 1001
6 = 0110
8 * 6 = 48
4 * 6 = 24
2 * 4 = 8
1 * 4 = 4
첫번째 자리 1의개수(3) * 0의개수(2) = 6
두번째자리 1의개수(2) * 0의 개수(3) = 6
세번째자리 1의개수(1) * 0의개수(4) = 4
네번째자리 1의개수(4) * 0의개수(1) = 4
예상한게 맞았다
이렇게 되면
같은 자리에 1과 0이 몇개 들어가는지 파악후 그 배열 자리에 맞는 비트연산자 값 * 개수 로 짜면 될 것같다.
package G3_Baekjoon;
import java.util.Scanner;
public class Baekjoon2830 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
long answer = 0; // 결과를 저장할 변수, 연산 결과가 int 범위를 넘을 수 있어서 long으로 선언
int[] count = new int[21]; // 2진수로 변환했을 때 각 자리수에서 1의 개수를 저장할 배열
// 각 숫자에 대하여
for (int i = 0; i < N; i++) {
int x = sc.nextInt(); // 숫자 입력
for (int j = 0; j < 21; j++) {
if ((x & (1 << j)) != 0) { // j번째 비트가 1인지 확인
count[j]++; // j번째 비트가 1이면 해당 자리수의 1의 개수를 증가
}
}
}
// 결과 계산
for (int i = 0; i < N; i++) {
for (int j = 0; j < 21; j++) {
// XOR 연산의 결과로 나올 수 있는 모든 경우의 수를 계산
// 각 자리수에서 1의 개수(count[j])와 0의 개수(N - count[j])를 곱하고
// 그 값에 2의 j승(해당 자리수가 표현하는 값)을 곱해서 answer에 더함
answer += (long) count[j] * (N - count[j]) * (1 << j);
count[j] = 0; // 해당 자리수의 1의 개수 초기화
}
}
System.out.println(answer);
}
}이런식으로 작성하면 됬다!
