인덱스 접근이 많다
랜덤 조회와 순차 스캔이 대부분이면 배열 계열이 캐시와 구현 면에서 유리하다.
연산 비율이 자료구조를 결정한다
배열과 리스트는 우열 문제가 아니라 조회, 삽입, 삭제 중 무엇이 지배적인지에 따라 선택한다.
앞/중간 변경이 잦다
앞 삽입이나 삭제가 반복되면 이동 비용을 피할 수 있는 덱, 리스트 계열을 검토한다.
입력 크기와 누적 비용
한 번의 비용보다 전체 연산 수에 곱해지는 비용이 시간 초과를 만든다.
A: 조회 80%, 변경 20%
기본 후보는 배열. 삭제 위치가 병목인지 추가 확인한다.
B: 조회 20%, 변경 80%
앞/중간 변경이 반복되면 리스트나 덱의 안정성이 커진다.