[알고리즘] XOR 비트 연산을 활용하기

[알고리즘] XOR 비트 연산을 활용하기

---

XOR 연산

 

비트 연산을 활용해서 문제에 적용하면 상당히 효율적으로 코딩이 가능한 경우가 있다.

특히 코딩테스트와 같이 문제를 풀 때 비트 연산을 활용하면 좋다.

 

이번에 살펴볼 예시는 보통 네이버나 카카오 등 프로그래머스를 이용해 코딩테스트를 보게 되는데, 테스트 환경에서 연습해보는 1번 문제로 등장하는 유형이다.

 

직사각형의 3개 점이 주어진다. 나머지 하나의 점의 좌표를 구하라.
(직사각형은 항상 평행한 상태)

ex)
(2, 0)
(6, 0)
(6, 6)

정답 : (2, 6)

 

다양한 방법을 이용해 푸는 것이 가능하지만, 가장 신박했던 방법은 비트연산을 활용해 푸는 것이었다.

 

XOR은 입력 값 중 하나만 true일 때 true를 리턴해준다.

 

따라서 주어진 3점의 x좌표와 y좌표를 각각 XOR 연산을 해주면 나머지 점의 값을 도출해낼 수 있다.

 

x1 = 2, y1 = 0
x2 = 6, y2 = 0
x3 = 6, y3 = 6

x = x1 ^ x2 ^ x3
y = y1 ^ y2 ^ y3

 

소스 코드

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class test {
    
    /*
     Input 값 (점의 개수, 각 점의 x좌표 y좌표)
     3
     2 0
     6 0
     6 6
    */
    
    public static void main(String[] args) throws Exception {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int N = Integer.parseInt(br.readLine());
        
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        
        int x = Integer.parseInt(st.nextToken());
        int y = Integer.parseInt(st.nextToken());
        
        for (int i = 0; i < N-1; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            
            //XOR연산
            x ^= Integer.parseInt(st.nextToken());
            y ^= Integer.parseInt(st.nextToken());
        }
        
        System.out.println(x + "," + y);
    }
 
}