O(n)에서 O(1)으로: Rock-Paper-Scissors 게임의 비효율적인 이동 횟수 계산 최적화

핵심 기술

이 글은 Rock-Paper-Scissors 게임에서 가장 흔한 움직임을 찾는 기능을 구현하며 발생한 O(n) 시간 복잡도의 성능 병목 현상을 O(1)로 개선하는 리팩토링 과정을 상세히 설명합니다. 핵심은 매번 전체 기록을 순회하는 대신, 움직임 횟수를 실시간으로 캐싱하고 업데이트하는 것입니다.

기술적 세부사항

• 문제점: 이전 구현에서는 determineMostCommonMove 함수가 매 호출 시마다 전체 플레이어 및 컴퓨터 이동 기록(history)을 순회하며 각 이동의 횟수를 세었습니다. 이는 이동 횟수(n)에 비례하는 O(n)의 시간 복잡도를 가집니다.
• 해결책: moveCounts 객체를 상태(state)에 추가하여 각 이동(rock, paper, scissors)의 횟수를 저장했습니다.
• 개선된 로직:
  • 새로운 이동이 발생할 때마다 해당 참가자(Participant)와 이동(StandardMove)에 맞는 moveCounts 값을 1씩 증가시킵니다 (incrementMoveCount 함수).
  • 가장 흔한 이동을 찾을 때는 moveCounts 객체를 순회합니다. 이 객체는 항상 고정된 크기(rock, paper, scissors, 총 3가지)를 가지므로, 시간 복잡도는 O(k) (여기서 k는 가능한 이동의 수)이며, 이는 상수 시간 O(1)로 간주됩니다.
• 타이 현상 처리: 여러 이동이 동일한 최대 횟수를 가질 경우 null을 반환하도록 로직을 수정하여, 명확한 '가장 흔한 이동'이 없을 때의 버그를 해결했습니다.

개발 임팩트

• 게임 규모가 커지거나 게임 라운드가 길어질수록 성능 저하를 방지할 수 있습니다.
• O(1) 시간 복잡도로 인해 실행 시간이 게임 기록의 길이에 전혀 영향을 받지 않아, 훨씬 빠르고 효율적인 응답성을 제공합니다.
• 코드의 가독성과 유지보수성이 향상됩니다.

커뮤니티 반응

원문에는 직접적인 커뮤니티 반응에 대한 언급은 없으나, 제시된 성능 개선 기법은 개발자 커뮤니티에서 일반적으로 중요하게 다루어지는 주제입니다.