[boj] 수업시간에 교수님 몰래 교실을 나간 상근이_2825 JAVA

문제는 다음과 같다.

나도 출튀를 참 즐겨했었지

 

숫자 N개를 입력받아, 숫자끼리 비교하며 0~9 중 같은 숫자가 쓰이는 경우가 있다면 ans++ 해주면 된다.

앗... 자리수가 0~9까지로 단 10자리?!

둘 다 있는지 비교?!

이것은...

비트마스킹.

과거의 나는 비트마스킹을 정말 싫어하였지만

이제는 그것도 다 옛말.

나는 비트의 몸을 맡기는 비트마스커 뤂시우가 되었다.

 

N개의 수를 입력받을 때, 각각의 자리수로 for문을 한 번 더 돌려, 해당하는 수의 위치의 비트를 1로 바꿔준다.

예를 들어, 비트를 바꾸기 전

int number = 0;

으로 설정해준다.

 

해당 number을 이진수로 표현하자면

number	9	8	7	6	5	4	3	2	1	0
여부	0	0	0	0	0	0	0	0	0	0

 

일 것이다.

 

만약 입력받은 수가 32라면

String temp = "32";

 

temp.length()로 for문을 돌렸을 때, 처음 temp.charAt(POINT) 은 '3'일 것이다.

그렇다면, 우리가 number에 적용해야 하는 숫자는

temp	9	8	7	6	5	4	3	2	1	0
여부	0	0	0	0	0	0	1	0	0	0

 

일 것이다.

따라서 1을 왼쪽으로 3번 shift연산 후,

 number |= temp.charAt(j) - '0';

 

number와 이를 합치면 된다!

 

2도 이와같이 진행하면, 최종적으로 number은

number	9	8	7	6	5	4	3	2	1	0
여부	0	0	0	0	0	0	1	1	0	0

1100 이렇게 될 것이다.

 

 

마찬가지로, 282도 이와같이 나타낼경우 

number	9	8	7	6	5	4	3	2	1	0
여부	0	1	0	0	0	0	0	1	0	0

100000100 이렇게 될 것이다. 마지막 2를 적용할 때, 이미 2가 1이 있지만 합집합 연산하면 그대로 1이 적용된다.

 

이 숫자들을 HashMap nums에 갯수와 함께 넣는다!

 

 

그 후, HashMap을 돌면서 같은 nums에 대해 1개 이상일 경우 ans를 업데이트 해준다.

        for (Map.Entry<Integer, Integer> entry:nums.entrySet()) {
            int num = entry.getKey();
            int cnt = entry.getValue();
            
            ans += (long)cnt*(cnt-1)/2; //cnt 중 순서 없이 2개 뽑기

 

이 num을 다른 HashMap내 num 들과 비교해아하는데, 중복 방지를 위해 현재의 num보다 큰 애들과 비교해준다.

비교하는 수를 num = 32, num2 = 282라고 가정해보자.

 

두 수는 "2" 라는 공통된 수를 갖고있다. 이는 비트마스킹 된 값으로 쉽게 찾을 수 있는데

num	9	8	7	6	5	4	3	2	1	0
여부	0	0	0	0	0	0	1	1	0	0

이것은 32의 nums 값이고,

num2	9	8	7	6	5	4	3	2	1	0
여부	0	1	0	0	0	0	0	1	0	0

이것은 282의 nums 값이다.

이 둘을 교집합연산 (&) 하면

num&num2	9	8	7	6	5	4	3	2	1	0
여부	0	0	0	0	0	0	0	1	0	0

공통으로 갖는 2만 1이되고, 나머지는 0이 됨을 알 수 있다.

 

따라서 num&num2 연산을 했을 시 0이 아니라면, 공통된 수를 갖고 있는 것이다!

이때는 num이 가지고있는 갯수 중 하나와, num2가 가지고 있는 갯수 중 하나를 뽑아야되기 때문에 nums.get(num) * nums.get(num2) 로 ans를 업데이트한다.

            for (int num2 : nums.keySet()) {
                if(num >= num2) continue; //num보다 작은 경우 continue처리
                if((num & num2) != 0) {
                    ans += (long) cnt*nums.get(num2);
                }
            }

 

이 과정을 모두 끝낸다면

 

맞으면 된다!

 

 

 

전체 코드

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

public class 수업시간에교수님몰래교실을나간상근이_2825 {
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(bf.readLine());
        Map<Integer, Integer> nums = new HashMap<>();

        for(int i = 0; i < N; i++) {
            String temp = bf.readLine();
            int number = 0;
            for(int j = 0; j < temp.length(); j++) {
                number |= 1 << (temp.charAt(j) - '0');
            }
            nums.put(number, nums.getOrDefault(number, 0) + 1);
        }

        long ans = 0;
        for (Map.Entry<Integer, Integer> entry:nums.entrySet()) {
            int num = entry.getKey();
            int cnt = entry.getValue();
            
            ans += (long)cnt*(cnt-1)/2;
            
            for (int num2 : nums.keySet()) {
                if(num >= num2) continue;
                if((num & num2) != 0) {
                    ans += (long) cnt*nums.get(num2);
                }
            }
        }
        System.out.println(ans);
    }
}