선택 흐름

문제 조건 세 문장만 읽어도 후보가 갈린다

질의 대상, 반복 횟수, 업데이트 유무를 차례로 보면 과한 자료구조 선택을 피할 수 있습니다.

01 질의 대상 확인 문자열 prefix인가, 배열의 [l, r] 범위인가?
02 반복 비용 확인 질의가 많아 선형 탐색이 병목이 되는가?
03 갱신 조건 확인 값 변경 후 다음 질의가 즉시 반영되어야 하는가?

prefix가 핵심이면 Trie

단어 존재, 접두사 존재, 자동완성 후보 수처럼 글자 경로를 내려갑니다.

search startsWith prefix count

구간 집계면 Segment Tree

합, 최솟값, 최댓값을 [l, r] 단위로 반복 질의하거나 갱신합니다.

range sum min/max update

반복 질의가 없으면 단순하게

한두 번만 계산하면 정렬, 누적합, 해시처럼 더 작은 도구가 충분할 수 있습니다.

sort prefix sum hash

5초 판정 “글자 경로”는 Trie, “인덱스 범위 집계”는 Segment Tree, 반복이 적으면 더 단순한 구조를 먼저 봅니다.