밥의 파이썬 게임 문제란?
친구 밥(Bob)이 혼자 하는 숫자 게임이 있다고 가정해 보겠습니다. 밥은 nums라는 숫자 리스트를 가지고 있으며, 매 턴마다 리스트에서 두 개의 원소를 선택한 뒤, 선택한 두 수의 합과 같은 값을 가지는 하나의 양의 정수로 교체합니다. 배열 안의 모든 숫자가 짝수가 되는 순간 밥은 승리를 선언할 수 있습니다.
우리가 구해야 할 값은 밥이 승리를 선언하기 위해 진행해야 하는 최소 턴 수입니다. 만약 아무리 시도해도 모든 수를 짝수로 만들 수 없다면 -1을 반환하면 됩니다.
예시
입력이 [2, 3, 4, 9, 7, 13]이라면 정답은 2입니다.
밥은 첫 번째 턴에 3과 9를 골라 합인 12로 바꾸고, 두 번째 턴에 7과 13을 골라 20으로 바꿀 수 있습니다. 그러면 리스트는 [2, 12, 4, 20]이 되어 모든 원소가 짝수가 됩니다.
해결 접근 방식
이 문제의 핵심은 홀수의 개수를 세는 것입니다. 두 수를 합칠 때 결과의 홀짝성은 다음과 같습니다.
- 짝수 + 짝수 = 짝수
- 홀수 + 홀수 = 짝수
- 홀수 + 짝수 = 홀수
즉, 한 번의 턴에서 홀수 두 개를 합쳐야만 홀수의 개수가 2개씩 줄어듭니다. 홀수와 짝수를 합하면 결과가 여전히 홀수이므로 홀수 개수는 줄어들지 않습니다.
따라서 다음과 같은 단계로 문제를 해결할 수 있습니다.
- 리스트에서 홀수만 골라 새로운 리스트 a를 만듭니다.
- a의 길이(홀수의 개수)가 짝수라면, 홀수들을 두 개씩 짝지어 합치면 되므로 정답은 len(a)/2입니다.
- a의 길이가 홀수라면 마지막에 홀수 하나가 반드시 남게 되어 승리 조건을 만족할 수 없으므로 -1을 반환합니다.
파이썬 구현 코드
아래 코드를 통해 실제 동작을 더 잘 이해할 수 있습니다.
class Solution:
def solve(self, nums):
a = [x for x in nums if x % 2 == 1]
if len(a) % 2 == 0:
return len(a) / 2
return -1
ob = Solution()
print(ob.solve([2, 3, 4, 9, 7, 13]))입력
[2, 3, 4, 9, 7, 13]출력
2복잡도 분석
리스트를 한 번만 순회하며 홀수를 세면 되므로 시간 복잡도는 O(n)입니다. 홀수를 저장하기 위해 추가 리스트를 사용하므로 공간 복잡도 역시 O(n)입니다.