문제 : [백준] 골드III_2830: 행성 X3
🤔 문제 분석
❓문제
- 이 행성에 사는 사람들의 이름은 모두 자연수이다.
- 행성의 거주민은 모두 서로를 알고 있다.
- 그들의 친밀도를 자신의 이름을 이진수로 바꾸어서 계산한다.
- 두 이름을 이진수로 바꾸고, 자리수가 짧은 쪽을 기준으로 정렬한다.
- 이때, 두 이진수의 각 자리 아래에 두 자리가 같으면 0을, 다르면 1을 적는다.
- 이진수를 다시 10진수로 바꾸면 그들의 친밀도가 된다.
행성의 가치는 이 섬에 있는 모든 친밀도의 합이다. 행성 거주민들의 이름이 주어졌을 때, 행성의 가치를 구하는 프로그램을 작성하시오.
✓ 입력 예시
N = 5| -- | 10진수 | Binary |
|---|---|---|
| (1) | 9 | 1001 |
| (2) | 13 | 1101 |
| (3) | 1 | 0001 |
| (4) | 9 | 1001 |
| (5) | 6 | 0110 |
1001 XOR 1101 => 0100 : 4 | 1001 XOR 0001 => 1000 : 8
1001 XOR 1001 => 0000 : 0 | 1001 XOR 0110 => 1111 : 151101 XOR 0001 => 1100 : 12 | 1101 XOR 1001 => 0100 : 4
1101 XOR 0110 => 1011 : 110001 XOR 1001 => 1000 : 8 | 0001 XOR 0110 => 0111 : 7
1001 XOR 0110 => 1111 : 15
총합 : 84
📝 풀이 설계
(1) 10진수 -> 2진수
(2) 2진수로 변환된 이름들 XOR연산(^)
(3) 2진수 -> 10진수(친밀도)로 변환
-> XOR연산자(^)를 쓸 때, 진수 변환이 따로 필요 없는 것 같다. 계산 후 결과를 자동으로 다시 10진수로 돌려준다.
(4) 총합+=각 친밀도
✍️ 내가 작성한 풀이
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[] names = new int[N];
int planetValue = 0;
// 주민들 이름 저장
for (int i = 0; i < N; i++) {
names[i] = (Integer.parseInt(br.readLine()));
}
// 모든 관계의 친밀도 계산(XOR 비트연산)하여 총합에 더해준다
for (int i = 0; i < N; i++) {
for (int j = i + 1; j < N; j++) {
planetValue += names[i] ^ names[j];
}
}
System.out.println(planetValue);
}
}
예시에 있는 케이스는 전부 통과했지만, 제출 시 시간 초과가 떴다.
문제 지문에 있는 (1 ≤ N ≤ 1,000,000)이라면 N이 1,000,000인 경우 엄청나게 많은 순회가 일어나야 하는 것이다.
그렇다면 어떻게 접근해야 더 효율적으로 주민들의 친밀도를 조사할 수 있을까?
❗️ 발견 내용
- 모든 이름을 이진수로 바꾸고 각 자릿수 마다 1의 개수를 센다.
- 자릿수 별로 1의 개수 0의 개수 2의 자릿수만큼의 제곱을 모두 더해주면 답을 구할 수 있다.
정리되어 있는 글을 찾다보니, 다들 같은 고민에 부딪히고 찾아보신 것 같다. 자세한 내용은 나와 있지 않았다. 그래서 한번 확인해 보기로 했다.
정상적으로 행성 가치를 계산했다. 이것을 활용하기 위해서는 주민들의 이름 전부 이진수로 변환하는 작업이 필요해보인다. 여러가지 방법들이 있었지만 어차피 각 자리수 1의 개수만을 구하면 되는 것이라 나머지가 1인 경우에 카운팅을 하는 방식으로 접근이 가능한 듯하다.
👀 다른사람 풀이 <- 약간 변경
import java.util.*;
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[] binaryCnt = new int[20];
int name;
int tmp = 0;
int idx;
long answer = 0L;
for (int i = 0; i < N; i++) {
name = Integer.parseInt(br.readLine());
idx = 0;
while (name != 0) {
tmp = name % 2;
name = name / 2;
if (tmp == 1) {
binaryCnt[idx]++;
}
idx++;
}
}
for (int i = 0; i < 20; i++){
planetValue += (1L << i) * binaryCnt[i] * (N - binaryCnt[i]);
}
br.close();
System.out.println(planetValue);
}
}
정리해주신 글들을 보고 이해하기로는 XOR연산은 값이 서로 달라야 1이 나온다. 각 자리수 마다 0과 1의 개수를 파악해서 0과 1 조합의 개수를 파악하면 된다. -> 1의 개수 x 0의 개수(N-1의 개수)
👍 코드 분석
int name;
int tmp = 0;
int idx;
long answer = 0L;
for (int i = 0; i < N; i++) {
name = Integer.parseInt(br.readLine());
idx = 0;
while (name != 0) {
tmp = name % 2;
name = name / 2;
if (tmp == 1) {
binaryCnt[idx]++;
}
idx++;
}
}입력받은 주민들의 이름을 입력받고, 인덱스 0 자리수 부터 해당 자리수 1의 개수를 카운팅(countOneArray[idx]++)
planetValue += (1L << i) * binaryCnt[i] * (N - binaryCnt[i]);
// `2^i x (해당 자리수 1의 개수) x (해당 자리수 0의 개수)`1L << i 가 왜 2^i 인가? 시프트 연산자(Shift Operator)이다. 우리는 해당 자리수의 십진수 값을 알고 싶은 것이기 때문에 해당 자리수 값에 해당되는 2^i에 해당하는 자리에 맞기 i만큼 시프트 연산 하는 것이다.
시프트 연산자(Shift Operator)
피연산자의 비트열을 왼쪽으로 이동시키며 이동에 따른 빈공간은 0으로 채운다.
💪 배운점
- 시간 복잡도에 대해 고려하지 못했던 것 같다. 다른분들의 블로그 글을 보면 주민의 수가 턱없이 많은 것을 보고 시간 복잡도로 인한 시간 초과를 우려하신 것 같다. 다음 문제에 접근할 때에는 시간복잡도에 대해 충분히 고려해봐야 할 것 같다.
- 이진수 - 십진수 관계, 비트 연산과 쉬프트 연산
- XOR 동작 방식에만 초점을 맞추는 것이 아니라 원하는 값을 도출해내기 위해, 어떤 동작이 필요한지 심도 있게 고민해봐야했다.
✅ 참고
