문제 개요
배열 nums와 한 쌍의 값 (x, y)가 주어졌을 때, 재귀적으로 정의된 find(x, y)의 값이 짝수인지 홀수인지 판별하는 문제입니다. find() 함수는 다음과 같이 정의됩니다.
- x > y이면 find(x, y) = 1
- 그 외의 경우에는 find(x, y) = nums[x] ^ find(x + 1, y)
예제로 이해하기
입력이 nums = [3, 2, 7]이고 (x, y) = (1, 2)라고 가정해 보겠습니다. 이 경우 출력은 짝수(Even)입니다. 그 과정은 다음과 같습니다.
- find(1, 2) = nums[1] ^ find(2, 2)
- find(2, 2) = nums[2] ^ find(3, 2)
- find(3, 2) = 1 (x > y 조건에 해당하므로)
- 따라서 find(2, 2) = 7 ^ 1 = 7이고, find(1, 2) = 2 ^ 7 = 128이 되어 짝수입니다.
해결 접근 방법
이 문제는 재귀 호출을 실제로 수행하지 않고도 몇 가지 조건만 확인해 상수 시간(O(1))에 해결할 수 있습니다. 다음 단계를 따릅니다.
- even 변수를 True로 초기화합니다.
- x > y이거나 nums[x]가 홀수라면 even을 False로 설정합니다.
- x가 배열 길이 - 1보다 작고, x < y이며, nums[x + 1]이 0과 같다면 even을 False로 설정합니다.
- even이 여전히 True이면 'Even'을 반환하고, 그렇지 않으면 'Odd'를 반환합니다.
구현 예제
아래 파이썬 구현을 통해 더 자세히 이해해 보겠습니다.
def solve(nums, x, y):
even = True
if x > y or (nums[x] % 2 == 1):
even = False
if x < len(nums) - 1 and x < y and nums[x+1] == 0:
even = False
if even:
return 'Even'
else:
return 'Odd'
nums = [3,2,7]
(x, y) = 1,2
print(solve(nums, x, y))
입력
[3,2,7], 1, 2
출력
Even
위 코드에서 첫 번째 조건은 기저 사례(x > y일 때 결과가 1, 즉 홀수)와 현재 위치의 요소가 홀수인 경우를 처리하고, 두 번째 조건은 다음 요소가 0일 때의 특수한 경우를 처리합니다. 이처럼 조건 검사만으로 재귀 없이 빠르게 답을 구할 수 있습니다.