연산 비율 선택 기준

연산 비율별 자료구조 선택 기준

조회, 삽입, 순서 보존 요구를 먼저 분리하면 리스트와 해시 집합의 선택 이유가 코드보다 먼저 정리됩니다.

조회 우세

존재 확인은 해시 후보

입력이 커질수록 선형 탐색 반복이 지배 비용이 되므로 평균 O(1) 조회 가능성을 먼저 계산합니다.

순서 요구

정렬 출력은 별도 비용

해시로 중복을 제거해도 결과 순서가 필요하면 정렬이나 순서 보존 구조가 추가됩니다.

최악 입력

충돌과 키 정책 확인

동일 키 처리, 대소문자 정규화, 충돌 가능성을 테스트 케이스에 넣어 선택을 확정합니다.

제출 전 남길 증거

선택 전 가장 많은 연산을 표로 적고, 그 연산의 입력 규모를 먼저 잡습니다.
구현 중 중복과 순서 의미가 바뀌는 지점을 작은 테스트로 바로 확인합니다.
제출 전 빈 입력, 한 원소, 전부 중복인 입력을 다시 넣어 선택을 검증합니다.