문제

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

정확히 두 개의 요소가 한 번만 나타나고 다른 모든 요소가 정확히 두 번 나타나는 숫자의 배열이 주어집니다. 한 번만 나타나는 두 가지 요소를 찾으십시오.

Example :

Input:   [1,2,1,3,2,5]
Output:  [3,5]

Note :

The order of the result is not important. So in the above example, [5, 3] is also correct.
Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

1.결과의 순서는 중요하지 않습니다. 위의 예에서 [5, 3]도 정확합니다

2.알고리즘은 선형 런타임 복잡성에서 실행되어야합니다. 일정한 공간 복잡성만 사용하여 구현할 수 있습니까?

기본 지식

비트연산 :

& 연산 :

& 연산자는 비트 AND이므로 두 비트가 모두 1일 때 1입니다. 따라서 하나라도 0이면 0이 나옵니다. 즉, 0000 0001과 0000 0011을 비트 AND 연산했을 때 0 & 1은 0 그리고 1 & 1은 1이 나오므로 0000 0001이 됩니다. 10진수로 표현하면 1 & 3은 1이 되겠죠?

비트 단위 &연산
ㅣ 연산 : | 연산자는 비트 OR이므로 두 비트 중 하나만 1이라도 1입니다. 따라서 두 비트가 모두 0일 때만 0입니다. 즉, 0000 0001과 0000 0011을 비트 OR 연산했을 때 0 | 1은 1 그리고 1 | 1은 1이 나오므로 0000 0011이 됩니다. 10진수로 표현하면 1 | 3은 3입니다.
^ 연산 : ^ 연산자는 비트 XOR이므로 두 비트가 다를 때 1입니다. 따라서 1과 1일 때, 0과 0일 때는 모두 0입니다. 즉, 0000 0001과 0000 0011을 비트 XOR 연산했을 때 0 ^ 1은 1 그리고 1 ^ 1은 0이 나오므로 0000 0010이 됩니다. 10진수로 표현하면 1 ^ 3은 2입니다.

&, |, ^ 연산결과
shift( » , « )연산 시프트 연산은 변수 « 이동할 비트 수 또는 변수 » 이동할 비트 수 형식으로 사용합니다. 즉 지정한 횟수대로 비트를 이동시키며 모자라는 공간은 0으로 채웁니다. 연산자 모양 그대로 «는 왼쪽, »는 오른쪽 방향입니다.

shift 연산

풀이

위 문제의 핵심은 요소의 갯수를 새어서 한 개인 요소를 두 개 찾는 것입니다. 여러가지 방법이 있습니다 단순하게 배열을 돌며 같은 수가 없으면 따로 저장해두어 찾는 방법, 앞의 방식은 두개의 for문을 써서 찾아야하지만 map을 사용하여 key에는 요소 value에는 갯수를 저장해두면 더 빨리 찾을 수가 있습니다. (예: 배열이 다음과 같이 주어지면 [1,2,1,2,3] , key : value 맵 { 1 : 2, 2 : 2, 3 : 1 } 로 value값이 1인 값을 찾는다.) 하지만, 위의 문제에서 일정한 공간복잡성을 이용해 문제를 해결하라고 했기 때문에 다른 방법으로 더 간단하게 해결해 보겠습니다.

비트연산 xor을 이용하면 쉽게 한 개인 요소를 찾을 수 있습니다 xor연산은 교환, 결합이 성립합니다. 따라서 [1,2,1,2,3]을 전부 xor연산 하면 1 ^ 2 ^ 1 ^ 2 ^ 3 = ( 1 ^ 1 ) ^ ( 2 ^ 2 ) ^ 3 = 3 즉, 한 개인 요소 3만 남게 됩니다. 위의 특징을 이용해 다음과 같은 순서로 문제를 해결하면 됩니다.

a a b b c d 전부다 XOR 연산 = c ^ d
c ^ d 비트연산 결과 숫자가 다르기 때문에, 적어도 한 비트는 “1”
그 1비트자리에서 c가 0이면 d는 1, 혹은 c가 1이면 d는 0
예 :
0000 0001 : 1
0000 0011 : 3
2번째 비트가 0,1로 다르다 이처럼 적어도 한 비트는 0,1로 다르다.
그 1비트자리를 기준으로 모든 원소를 두 그룹으로 나누고 나눈 그룹에 각각 XOR연산하면 그룹당 1개인 요소가 추출됩니다.

Answer :

class Solution {
    public int[] singleNumber(int[] nums) {
        int xor = 0;
        
        for(int num:nums) xor^=num;   				// 1.
        
        int idx = 0;						//
								//
        for(int i=0; i < 32 ; i ++)				//
        {							//
            if(((xor>>i) & 1) == 1 ){				// 2. 
                idx = i;					//
                break;						//
            }							//
        }							//
        
        int xor1 = 0;
        int xor2 = 0;
        
        for(int num: nums){					//
            if(((num >> idx) &1) == 1){				//
                xor1 ^= num;					//
            }else{						// 3.
                xor2 ^= num;					//
            }							//
        }							//
        
        int[] result = new int[2];
        result[0] = xor1;
        result[1] = xor2;
        return result;
    }
}

이해를 돕기 위해 [1,2,3,1,2,5]를 대입해 설명하도록 하겠습니다.

1. 에서 요소의 갯수가 두 개인 1,2는 없어지고 3 ^ 5 만 남습니다.

2. 3 ^ 5 연산 결과
0000 0011 : 3
0000 0101 : 5
0000 0110 : xor
2,3번째 비트가 다르고 for문으로 shift, &연산을 이용해 “1”인 비트를 찾습니다

따라서, idx는 “2”가 될 것입니다. ( 2번째 비트가 3번째 비트 보다 먼저이기 때문에 break )

3. 2번째 비트가 1인 숫자 ( 2, 3 ), 2번째 비트가 0인 숫자 ( 1, 5 ) 두 그룹으로 나뉘어서 xor연산 됩니다.
2번째 비트가 1인 xor1 ^= num 은 2 ^ 2 ^ 3으로 3이 추출
2번째 비트가 0인 xor2 ^= num 은 1 ^ 1 ^ 5으로 5가 추출됩니다.

출처 : 제가 알고리즘 문제에 막 감을 익히고 있는 단계여서 유튜버 승지니어님의 코드를 많이 인용하였습니다. 도움되는 영상이 많이 있으므로 많은 방문 부탁드리겠습니다.

유튜브 승지니어 해당영상

← Previous Post Next Post →

LeetCode#260

Single Number III

문제

기본 지식

풀이