Computer >> 컴퓨터 >  >> 프로그래밍 >> Python

파이썬(Python)으로 생성된 리스트에서 특정 요소의 XOR 값 찾기

자연수로 이루어진 리스트가 하나 주어져 있다고 가정해 보겠습니다. 이 리스트에서 이진수 표현상 연속된 두 개의 1을 포함하는 숫자를 모두 제거하여 새로운 리스트 Z를 생성합니다. 이후 정수 값들을 담고 있는 또 다른 리스트 'input_list'가 주어지면, Z에서 해당 인덱스에 위치한 요소들을 찾아 그들의 XOR 값을 계산해야 합니다.

예를 들어 입력이 input_list = [3, 4, 5]라면 결과는 9가 됩니다.

Z의 인덱스 3, 4, 5에 해당하는 값은 각각 4, 5, 8입니다. 따라서 4 XOR 5 XOR 8 = 9가 됩니다.

참고로 이진수에서 연속된 1이 나타나지 않는 수를 '피바이너리(fibbinary) 수'라고 부르며, 이러한 수의 분포는 피보나치 수열과 깊은 관련이 있습니다. 이 성질을 활용하면 거대한 리스트 Z를 실제로 만들지 않고도 특정 인덱스의 값을 즉시 계산할 수 있어 매우 효율적입니다.

해결 절차

이 문제를 해결하기 위해 다음 단계를 따릅니다 −

  • zeck_num() 함수를 정의합니다. 이 함수는 k와 f_list를 인자로 받습니다.
    • res := 0으로 초기화합니다.
    • i를 f_list의 크기 - 1부터 -1까지 1씩 감소시키며 반복합니다.
      • k >= f_list[i]라면:
        • res := res + 2^i
        • k := k - f_list[i]
    • res를 반환합니다.
  • MOD := 10^9 + 7로 설정합니다.
  • max_val := 10^18로 설정합니다.
  • f_list := 값 1과 2를 포함하는 새로운 리스트를 만듭니다.
  • f_list의 마지막 원소가 max_val 이하인 동안 다음을 반복합니다.
    • f_list의 마지막 원소와 뒤에서 두 번째 원소의 합을 f_list 끝에 추가합니다.
  • res := 0으로 초기화합니다.
  • input_list의 각 인덱스에 대해 다음을 수행합니다.
    • res := res XOR zeck_num(index, f_list)
  • res mod MOD를 반환합니다.

예제

아래 구현을 통해 더 잘 이해해 보겠습니다 −

def zeck_num(k, f_list):
    res = 0
    for i in range(len(f_list)-1,-1,-1):
        if k >= f_list[i]:
            res += 2**i
            k -= f_list[i]
    return res

def solve(input_list):
    MOD = 10**9+7
    max_val = 10**18
    f_list = [1,2]
    while f_list[-1] <= max_val:
        f_list.append(f_list[-1] + f_list[-2])
    res = 0
    for index in input_list:
        res ^= zeck_num(index, f_list)
    return res % MOD

print(solve([3, 4, 5]))

입력

[3, 4, 5]

출력

9