HackerRank - LonelyInteger

이 문제는, LeetCode에도 동일한 문제가 있다.

가장 중요한 부분은 비트연산자를 사용해야 간단히 풀린다는거.

 

1. 문제 

https://www.hackerrank.com/challenges/one-month-preparation-kit-lonely-integer/problem?isFullScreen=true&h_l=interview&playlist_slugs%5B%5D=preparation-kits&playlist_slugs%5B%5D=one-month-preparation-kit&playlist_slugs%5B%5D=one-month-week-one 

Lonely Integer | HackerRank

 

문제는 결국 배열이 들어오면 동일한 값을, 체크해야 한다는 점이 포인트인데, 이를 비트 연산으로 풀줄은 상상도 못했다. 원래 배열을 별도로 만들어서 카운트 값으로 구분해서, 카운트가 2가 아닌 값을 리턴하게 하려고 했는데, 안됐다..

 

2. 문제 풀이

def lonelyinteger(a):
    res = 0
    for i in a:
        res = res^i
    return res

비트연산의 XOR을 이용하면 쉽게 풀 수 있다.

비트 연산의 XOR의 경우 같은 비트이면 0, 다른 비트이면 1이다.

따라서 A^A의 경우 같은 비트이므로 0이되고, 

A^A^B의 경우 0^B가 되므로 B가 도출된다.

 

이런식으로 진행이 되면 예를 들어 a = [1, 1, 2, 2, 3] 이라고 하면 1^1^2^2^3 => 3만 남게된다.

 

문제를 볼 때 다양한 방식으로 생각해보는 게 필요한 것 같다. 비트 연산 복습해야겠다!