[코드트리/INTERMEDIATE LOW] xor 결과 최대 만들기 (JAVA)

🔺 문제

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

 

 

🧩  해결 아이디어

• 백트래킹

1. N개 중 M개를 뽑는 가능한 모든 조합을 만든다.

2. 해당 조합에 대해 XOR 연산을 수행하고, 이 중 최댓값을 구한다.

 

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int max = Integer.MIN_VALUE;
 
    static int N, M;
    static int[] arr;
    static List<Integer> comb = new ArrayList<>();
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
 
        arr = new int[N];
        st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0 ; i <  N ; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);
 
        getComb(0, 0);
        System.out.println(max);
    }
 
    private static void getComb(int lastNum, int depth) {
        if(depth == M) {
            max = Math.max(max, XOR());
            return;
        }
 
        for(int i = lastNum ; i < N ; i++) {
            comb.add(arr[i]);
            getComb(i + 1, depth + 1);
            comb.remove(comb.size() - 1);
        }
    }
 
    // XOR 비트 연산 메소드
    private static int XOR() {
        int tmp = comb.get(0);
 
        for(int i = 1 ; i < comb.size() ; i++) {
            tmp = tmp ^ comb.get(i);   // XOR 비트 연산
        }
 
        return tmp;
    }                                                                                                                                                     
}

 

 

---

🔺 다른 풀이들

1) N개 중 M개 뽑는 모든 조합 만들고, 각각의 조합에 대해 XOR 연산 수행

- 시간 복잡도 : O(조합(N, M) * M)

private static void solve(int currIdx, int depth) {
    if(depth == M) {
        max = Math.max(max, XOR());
        return;
    }

    // currIdx에 있는 숫자 선택하지 않은 경우
    solve(currIdx + 1, cnt);

    // currIdx에 있는 숫자 선택한 경우
    visited[currIdx] = true;
    solve(currIdx + 1, cnt + 1);
    visited[currIdx] = false;
}

 

 

2) 재귀 함수 인자로 currVal 값 가져가며 업데이트  ✅

- 시간 복잡도 : O(조합(N, M))

┕ currIdx 위치의 숫자 선택 시,      그 다음 재귀 함수 인자 값으로 currVal ^ arr[ currIdx ]한 값 보냄

┕ currIdx 위치의 숫자 선택  X 시, 그 다음 재귀 함수 인자 값으로 기존 currVal 그대로 보냄

private static void solve(int currIdx, int depth, int currVal) {	// currVal 갖고 다니며 업데이트
    if(depth == M) {
        max = Math.max(max, currVal);	// 🔔
        return;
    }

    // currIdx에 있는 숫자 선택하지 않은 경우
    solve(currIdx + 1, cnt, currVal);

    // currIdx에 있는 숫자 선택한 경우
    solve(currIdx + 1, cnt + 1, currVal ^ arr[currIdx]);
}

---

💬 느낀 점

XOR 연산을 배우다...

어렵지만 재미있는 백트래킹의 나라...

 

 

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

---

(참고)

✔ 비트연산, XOR 연산 참고

[알고리즘] java 비트연산 정리하기

Java - XOR 연산자

07. [자바] 비트 연산자 &, |, ^, ~, <<, >>