Pre-computed Array 도입을 통한 이동 처리 시간 O(N)에서 O(1)로 단축

Java LLD: Designing Snakes and Ladders with O(1) Move Resolution

Machine coding Master2026년 6월 26일2분intermediate

AI 요약

Context

보드 게임의 이동 로직 구현 시 각 턴마다 Snake와 Ladder 리스트를 순회하는 $O(N)$ 탐색 방식의 성능 저하 발생. Board 메커니즘과 Game Loop가 결합된 Monolithic 구조로 인해 요구사항 변경 시 확장성 결여 및 SRP 위반 문제 직면.

보드 전체를 Flat한 Primitive Array로 정의하여 각 인덱스에 최종 목적지를 미리 저장하는 Pre-computation 전략 채택
Runtime Lookup 과정을 단순 Array Access로 대체하여 $\text{resolvePosition}$ 함수의 시간 복잡도를 $O(1)$로 최적화
MovementStrategy 인터페이스를 도입하여 주사위 규칙 및 추가 턴 로직을 Core 클래스와 분리한 OCP 준수 설계
Jump 엔티티를 통해 Snake와 Ladder를 추상화하고 Board 초기화 단계에서 목적지 맵핑을 완료하는 구조 구축
단순 셀 이동에 무거운 Object Graph 대신 Cache-friendly한 Primitive Array를 사용하여 메모리 효율성 및 처리 속도 향상

실천 포인트

1. 반복적인 조건 체크가 발생하는 런타임 경로를 Pre-computed Table로 대체 가능한지 검토

2. 비즈니스 규칙 변경이 잦은 로직을 Strategy 패턴으로 분리하여 Core 도메인 보호

3. 단순 데이터 참조 시 객체 그래프보다 Primitive Array 기반의 메모리 레이아웃 최적화 고려

태그