유형별 엣지케이스 체크리스트
Summary
제출 직전에 보는 파일이다.
알고리즘을 맞게 골라도 경계조건과 Java 메서드 방향을 놓치면 틀린다.
BFS / DFS
N = 1, M = 1인가?
시작점이 이미 도착점인가?
시작점/도착점이 벽인가?
4방향인가 8방향인가?
여러 시작점에서 동시에 BFS인가?
visited를 offer 때 체크하는가?
그래프가 끊겨 있는가?
재귀 DFS 깊이가 커서 StackOverflow 위험은 없는가?Stack / Queue / Deque
큐처럼 쓰는데 push()를 쓰지 않았는가?
push()는 앞에 넣는 동작임을 확인했는가?
offer()/offerLast()는 뒤에 넣는 동작임을 확인했는가?
poll()/pollFirst()는 앞에서 꺼내는 동작임을 확인했는가?
stream().mapToInt(i -> i).toArray() 결과는 현재 앞 → 뒤 순서인가?
스택처럼 push()로 넣었다면 배열 변환 시 삽입 역순이 되는가?
ArrayDeque에 null을 넣지 않는가?
poll/peek 결과 null을 int로 바로 언박싱하지 않는가?
remove/get 계열은 빈 덱에서 예외가 난다는 점을 확인했는가?
방향이 필요한 문제에서 offerFirst/offerLast/pollFirst/pollLast를 명시했는가?그래프 / 최단경로
시작 == 도착인가?
도달 불가능한 노드는 어떻게 출력하는가?
중복 간선이 있는가?
자기 루프가 있는가?
간선 비용 합이 int를 넘는가?
음수 간선이 있는가?
Dijkstra를 쓰면 안 되는 조건인가?
Floyd에서 INF + INF를 더하지 않도록 guard 했는가?
0-1 BFS에서 비용 0은 offerFirst, 비용 1은 offerLast인가?Union-Find / MST
정점 번호가 0부터인가 1부터인가?
이미 같은 집합이면 union을 건너뛰는가?
MST에서 선택 간선 수가 V - 1개인지 확인했는가?
모든 정점 연결이 불가능한 경우가 있는가?
비용 합은 long인가?이분탐색 / 매개변수 탐색
빈 배열인가?
target이 모든 값보다 작은가?
target이 모든 값보다 큰가?
중복 값이 있는가?
mid 계산에서 overflow가 날 수 있는가?
left/right가 무한 루프에 빠지지 않는가?
can(mid)가 단조성을 가지는가?
최댓값을 찾는지 최솟값을 찾는지에 따라 left/right 이동이 맞는가?투포인터 / 누적합
음수가 있으면 투포인터를 쓰면 안 되는가?
연속 구간이 빈 구간을 허용하는가?
left <= right 조건이 맞는가?
누적합이 int를 넘는가?
부분합 개수는 long이어야 하는가?
HashMap 누적합에서 prefix 0을 미리 넣었는가?DP
dp[i]의 의미가 한 문장으로 정의되는가?
dp[0], dp[1], dp[2] 초기값을 직접 세었는가?
i-1, i-2 접근에서 음수 인덱스가 나는가?
정답이 dp[N]인가, max(dp)인가?
경우의 수면 mod를 적용했는가?
1차원 최적화 시 순회를 앞에서 해야 하는가, 뒤에서 해야 하는가?백트래킹 / 비트마스크
R = 0인가?
R = N인가?
중복 원소를 같은 값으로 볼지 다른 인덱스로 볼지 정했는가?
가지치기 조건이 정답을 제거하지 않는가?
N >= 31이면 1 << N이 overflow 나는가?
long mask가 필요한가?PriorityQueue / 정렬
Java PriorityQueue 기본이 최소힙임을 확인했는가?
최대힙이면 Collections.reverseOrder() 또는 Comparator를 썼는가?
Comparator에서 a - b를 쓰지 않았는가?
정렬 기준이 1순위/2순위까지 맞는가?
동률 처리 때문에 답이 달라지지 않는가?Java 공통
Scanner를 써도 되는 입력 크기인가?
StringBuilder로 출력 누적했는가?
Comparator에서 a - b를 쓰지 않았는가?
Integer는 == 대신 equals 또는 int 변환으로 비교했는가?
String을 반복 +로 붙이지 않았는가?
2차원 배열 clone이 얕은 복사라는 점을 확인했는가?
split(" ")이 연속 공백에서 빈 문자열을 만들 수 있지 않은가?