파이썬으로 푸는 Single Number II: 세 번 등장하는 배열에서 유일한 숫자 찾기

문제 개요

정수로 이루어진 비어 있지 않은 배열이 하나 주어집니다. 배열의 모든 원소는 정확히 세 번씩 등장하지만, 단 하나의 원소만 딱 한 번 등장합니다. 이때 그 유일한 원소를 찾아야 합니다. 예를 들어 배열이 [2,2,3,2]라면 출력 결과는 3이 됩니다.

해결 접근 방식

이 문제는 비트 연산과 모듈로(나머지) 계산을 활용하면 효율적으로 해결할 수 있습니다. 각 숫자를 이진수로 표현했을 때 비트별로 1이 나타난 횟수를 누적하고, 그 값을 3으로 나눈 나머지를 구하면 세 번 등장한 숫자들의 기여는 모두 사라지고 한 번만 등장한 숫자의 비트 정보만 남게 됩니다.

구체적인 알고리즘 단계는 다음과 같습니다.

배열 원소들의 절댓값 중 최댓값을 구해 max_num에 저장합니다.
max_bits := log₂(max_num)의 정수 부분 + 2로 설정합니다.
max_bits 크기의 리스트 list1을 생성하고 모든 요소를 0으로 초기화합니다.
nums의 각 숫자에 대해 다음 과정을 반복합니다.
- pos := 0으로 초기화합니다.
- num이 0이 아니고 pos가 max_bits 미만인 동안 반복합니다.
  - 숫자가 홀수(최하위 비트가 1)이면 list1[pos]를 1 증가시킵니다.
  - n := n / 2(오른쪽 시프트)를 수행하고 pos를 1 증가시킵니다.
i를 0부터 max_bits까지 순회하며 list1[i] := list1[i] mod 3을 적용합니다.
pos := 0, res := 0으로 초기화합니다.
i를 0부터 max_bits까지 순회하면서 list1[i]가 0이 아니면 result += 2^pos를 수행하고, pos를 1 증가시킵니다.
list1[max_bits - 1]이 1이라면(음수 판별), res := -(2^max_bits - res)로 변환합니다.
res를 반환합니다.

파이썬 구현 예제

다음 구현 예제를 통해 더 자세히 이해해 보겠습니다.

import math

class Solution(object):
    def singleNumber(self, nums):
        max_num = max(map(abs, nums))
        max_bits = (int)(math.log(max_num, 2)) + 2
        list1 = [0 for i in range(max_bits)]
        for no in nums:
            pos = 0
            while (no != 0 and pos < max_bits):
                if (no & 1 != 0):
                    list1[pos] += 1
                no >>= 1
                pos += 1
        for i in range(max_bits):
            list1[i] %= 3
        pos = 0
        result = 0
        for i in range(max_bits):
            if (list1[i] != 0):
                result += (2 ** pos)
            pos += 1
        print(list1, max_bits)
        if (list1[max_bits - 1] == 1):
            result = -(2 ** max_bits - result)
        return (result)

ob = Solution()
print(ob.singleNumber([2,2,3,2]))

입력

[2,2,3,2]

출력

[1, 1, 0] 3
3

출력 결과 분석

위 실행 결과에서 [1, 1, 0]은 각 비트 위치별로 1이 등장한 횟수를 3으로 나눈 나머지입니다. 이진수로 읽으면 '11', 즉 십진수 3이 되며, 이것이 바로 배열에서 한 번만 등장한 숫자입니다. 최종 출력값도 3으로 정상적으로 반환되었음을 확인할 수 있습니다.