[C#] 137. Single Number II

 

1. 문제

 

한 번만 나타나는 한 개의 요소를 제외한 모든 요소들이 3번씩 나타나는 배열인 nums가 주어진다.

한 번만 나타나는 요소를 찾아 리턴하면 된다.

 

선형 복잡도를 가지고 일정한 메모리만 사용하는 솔루션을 구현해야 한다.

 

 

---

 

2. 풀이 과정

 

인자로 들어오는 배열의 크기가 커지면 커질수록 수행 시간이 늘어나야 한다니 단순히 for문을 작성하면 될 것 같다고 생각했다.

 

주목해야 하는 점이 있다면

1. 찾아내야 하는 하나의 요소를 제외한 모든 요소는 3번 나타난다.

2. 같은 숫자는 XOR 연산을 해버리면 0이 된다.

 

위의 두 가지를 결합하여 생각한다면

 

배열을 오름차순 or 내림차순으로 정렬 후 3개 단위로 검사하면서 3개 중 앞의 두 요소를 XOR 연산했을 때 0이 아니라면 3개 중 맨 앞의 요소는 문제가 원하는 답이 된다.

 

nums의 길이를 n이라고 했을 때 인덱스 n - 4와 n - 3을 비교할 때까지 정답이 나오지 않았다면 답이 되는 요소는 배열의 맨 뒤에 있다는 뜻이므로 이들을 고려하여 코드를 작성하면

 

public class Solution {
    public int SingleNumber(int[] nums)
    {
        var length = nums.Length - 1;
        if (length == 0)
            return nums[0];

        Array.Sort(nums);

        for(int i = 0; i < length; i += 3)
        {
            if ((nums[i] ^ nums[i + 1]) != 0)
                return nums[i];
        }

        return nums[length];
    }
}