Single Number

https://leetcode.com/problems/single-number/description/

 

비트 조작 문제이다. 비트 연산자는 잘 사용하지 않았지만, 기본적인 원리 정도는 이해하고 있었다.

해당 카테고리를 보고 비트 연산자를 복습한 이후 문제 풀이를 진행했다.

 

java에서는 &, |, ^, ~ 를 비트 논리 연산자로 사용할 수 있다. 비트를 이동 시키는 연산자도 있지만 해당 문제를 해결하기 위해선 비트 논리 연산자를 이해하면 된다.

 

& 의 경우 비트의 값이 모두 1일 경우 1을 반환한다.(AND)
| 의 경우 비트의 값 중 하나가 1일 경우 1을 반환한다.(OR)
^의 경우 비트의 값이 다를 경우(0, 1), (1, 0) 일 경우 1을 반환한다.(XOR)
~의 경우 비트의 값을 반대로 변환한다.(NOT)

 

해당 문제를 해결하기 위해선 XOR 연산자가 적절하였다. 개인적으로는 4가지 논리에서 가장 생소한 부분으로 느껴지기도 했지만 문제를 읽고서 해당 논리 연산자가 필요한 것을 알 수 있었다.

 

문제는 한 번 등장한 값을 반환하는 것이 목표이다.
기본 시작 값을 0으로 하여, 값들에 XOR 연산자를 더 할 경우 첫 번째 등장 시에는 비트에 값이 1로 새겨지며 더해지겠지만, 두번째 값이 등장 시 비트를 0으로 바꾸어 값을 지우게 된다. 최종적으로 한 번 등장한 값만 비트에 값을 새기며 정답의 2진수에 맞게 된다. 서로 다른 값이 같은 비트를 수정한다 하더라도 짝수 번 반복하여 값을 지우기 때문에 다른 값이 같은 비트를 수정하는 경우도 문제가 되지 않는다. 아래는 비트 논리 연산자를 사용하여 해당 문제를 해결한 코드이다.

public class Solution {  
    public int singleNumber(int[] nums) {  
        int answer = 0;  
  
        for(int num : nums){  
            answer = answer^num;  
        }  
  
        return answer;  
    }  
}