[코드트리/INTERMEDIATE HIGH] 겹치는 bit가 없는 세 수 (JAVA)

📖 문제

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

💡  풀이 방식

• 비트마스크

1. 서로 다른 3개의 숫자를 고른다. (완전탐색)

2. 세 숫자의 bit가 서로 겹치지 않는지 확인한다. (& 연산자 활용해 결과가 0인지 확인)

// bit가 서로 겹치지 않음 = & 연산하고 결과가 0일 때
private static boolean chkBitOverlap(int a, int b, int c) {
    return ((a & b) == 0 && (a & c) == 0 && (b & c) == 0);
}

 

3. 세 숫자의 bit가 서로 겹치지 않는 경우, 세 수의 합을 구하고 이를 최댓값과 비교해 갱신한다.

 

 

💥 유의사항

(a & b & c)하면 무조건 0이 나오고, 이렇게 비교하면 아니 된다..

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int max = 0;
 
    static int N;
    static int[] arr;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        N = Integer.parseInt(br.readLine());
        arr = new int[N];
 
        st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0 ; i < N ; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
 
        // 숫자 3개 고르기 (완탐)
        for(int i = 0 ; i < arr.length - 2 ; i++) {
            for(int j = i + 1 ; j < arr.length - 1 ; j++) {
                for(int k = j + 1 ; k < arr.length ; k++) {
                    if(chkBitOverlap(arr[i], arr[j], arr[k]) && (getSum(arr[i], arr[j], arr[k]) > max)) {
                        max = getSum(arr[i], arr[j], arr[k]);
                    }
                }
            }
        }
 
        System.out.println(max);
    }
 
    // bit가 서로 겹치지 않음 = & 연산하고 결과가 0일 때
    private static boolean chkBitOverlap(int a, int b, int c) {
        return ((a & b) == 0 && (a & c) == 0 && (b & c) == 0);
    }
 
    private static int getSum(int a, int b, int c) {
        return a + b + c;
    }
}

 

 

➕ 다른 풀이 방식

숫자 3개 고를 때 조합(dfs)을 활용해봤다..

권장하지 않는다..

(1024ms, 80MB)

import java.util.*;
import java.io.*;
 
public class Main {
    static int max = 0;
 
    static int N;
    static int[] arr;
    static List<Integer> list = new ArrayList<>();
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        N = Integer.parseInt(br.readLine());
        arr = new int[N];
 
        st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0 ; i < N ; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
 
        // 숫자 3개 고르기 (조합)
        comb(0, 0);
        System.out.println(max);
    }
 
    // 숫자 3개 고르는 메소드 (조합, dfs)
    private static void comb(int idx, int depth) {
        if(depth == 3) {
            if(chkBitOverlap()) {
                max = Math.max(max, getSum());
            }
            return;
        }
 
        for(int i = idx ; i < arr.length ; i++) {
            list.add(arr[i]);
            comb(i + 1, depth + 1);
            list.remove(list.size() - 1);
        }
 
        return;
    }
 
    // bit가 서로 겹치지 않음 = & 연산하고 결과가 0일 때
    private static boolean chkBitOverlap() {
        int a = list.get(0);
        int b = list.get(1);
        int c = list.get(2);
 
        return ((a & b) == 0 && (a & c) == 0 && (b & c) == 0);
    }
 
    private static int getSum() {
        int sum = 0;
        for(int i : list) {
            sum += i;
        }
        return sum;
    }
}

---

💦 어려웠던 점

- 처음에 숫자 3개를 한 번에 and 연산자로 묶어서 결과가 0인지 확인하려고 했다.

(a & b & c) == 0; // (X)

 

그런데 그러면 무조건 값이 0이 나와서 틀리고,

2개씩 묶어서 값이 0인지 확인해야 했다.

(a & b) == 0 && (b & c) == 0 && (c & a) == 0	// (O)

 

 

1회독	2회독	3회독	4회독	5회독
V