Java 코딩테스트 치트시트

문서 목적

Java 기반 코딩테스트에서 자주 쓰는 문법·자료구조·수학 공식을 빠르게 찾아보기 위한 참고 문서.
BFS/DFS, 이분 탐색 등 알고리즘 풀이 템플릿은 별도 문서로 관리한다.

1. 수학 공식과 Math

1.1 카테고리별 선택의 경우의 수

여러 카테고리에서 카테고리당 최대 하나씩 선택하고, 최소 하나는 골라야 할 때 사용한다.

(a + 1) × (b + 1) × (c + 1) - 1

• a, b, c: 각 카테고리의 원소 개수
• +1: 해당 카테고리를 선택하지 않는 경우
• -1: 아무것도 선택하지 않는 경우 제외
• 대표 문제: 프로그래머스 의상

주의

이 공식은 모든 조합 문제에 적용되는 일반적인 조합 공식 nCr이 아니다. 각 카테고리에서 0개 또는 1개를 고르는 조건일 때 사용한다.

1.2 최대공약수(GCD)와 최소공배수(LCM)

두 주기가 다시 일치하는 시점, 공통 배수 등을 구할 때 사용한다.

int gcd(int a, int b) {
    if (b == 0) return Math.abs(a);
    return gcd(b, a % b);
}
 
// a, b가 양수인 경우; 중간 곱셈 오버플로 방지
long lcm = (long) a / gcd(a, b) * b;

• 유클리드 호제법: gcd(a, b) = gcd(b, a % b)
• 공식: LCM(a, b) = |a × b| / GCD(a, b) (두 수가 0이 아닌 경우)
• 예: A는 3일마다, B는 4일마다 반복 → 12일마다 일치

1.3 등차수열의 합

합 = n × (first + last) / 2

• n: 항의 개수, first: 첫 항, last: 마지막 항
• 예: 1부터 100까지 합 = 100 × (1 + 100) / 2 = 5050

long sum = (long) n * (first + last) / 2;

오버플로

first + last도 int를 초과할 수 있다면 (long) first + last로 계산한다.

1.4 소수 판별

소수 여부는 2부터 √N까지 나누어 떨어지는지 검사한다. 시간 복잡도 O(√N).

boolean isPrime(int n) {
    if (n < 2) return false;
    for (int i = 2; (long) i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

약수는 서로 짝을 이루므로 제곱근을 넘어서까지 검사할 필요가 없다.

1.5 나머지 연산(Mod)

int remainder = num % n;

• num >= 0, n > 0일 때 결과는 0 ~ n-1
• 활용: 원형 배열, 순환 인덱스, 해시 연산
• Java에서 음수에 %를 적용하면 음수 나머지가 나올 수 있다.

int index = Math.floorMod(num, n); // n > 0: 항상 0 ~ n-1

1.6 주요 수학 함수

함수	의미	예시 / 참고
Math.pow(a, b)	거듭제곱	반환형 double
Math.sqrt(a)	제곱근	반환형 double
Math.abs(a)	절댓값	Math.abs(Integer.MIN_VALUE) 주의
Math.min(a, b)	최솟값
Math.max(a, b)	최댓값
Math.ceil(1.2)	올림	2.0 (double)
Math.floor(1.8)	버림(음의 무한대 방향)	1.0 (double)
Math.round(1.5)	반올림	2 (long이 아닌 int, 인자가 double인 경우 long)
Integer.compare(a, b)	정수 크기 비교	뺄셈 비교의 오버플로 방지

int[] arr = {1, 2, 3};
int sum = Arrays.stream(arr).sum();
double avg = Arrays.stream(arr).average().orElse(0);

1.7 진법 변환

Integer.toBinaryString(n); // 2진수 문자열
Integer.toOctalString(n);  // 8진수 문자열
Integer.toHexString(n);    // 16진수 문자열
 
Integer.parseInt("1010", 2); // 10
Integer.parseInt("12", 8);   // 10
Integer.parseInt("a", 16);   // 10

---

2. 문자열 String

메서드	설명
str.length()	문자열 길이
str.substring(s, e)	s 이상 e 미만 부분 문자열
str.charAt(idx)	특정 위치 문자 (char)
str.equals(other)	문자열 내용 비교
str.split("")	문자를 단위로 분리한 String[] (정규식 기반)
str.toCharArray()	char[]로 변환
new String(chars)	char[]를 String으로 변환
a.compareTo(b)	사전식 비교: 음수 / 0 / 양수
String.join("", arr)	문자열 배열 이어 붙이기

String str = "123";
int num = Integer.parseInt(str);
Integer boxed = Integer.valueOf(str);
String text = Integer.toString(num);
 
char[] chars = {'J', 'a', 'v', 'a'};
String word = new String(chars); // "Java"
 
String[] names = {"Lee", "Kim"};
int idx = Arrays.asList(names).indexOf("Kim"); // 1, 없으면 -1

문자열 조합 기준 정렬: 가장 큰 수

String[] stringNums = {"3", "30", "34", "5", "9"};
Arrays.sort(stringNums, (a, b) -> (b + a).compareTo(a + b));

• a + b와 b + a 중 어떤 연결 순서가 큰지 비교한다.
• 일반적인 개별 숫자 크기 정렬과는 다른 규칙이다.
• 입력에 0만 있다면 결과를 "0"으로 처리하는 예외가 필요할 수 있다.

---

3. StringBuilder

문자열을 반복해서 추가·수정할 때 불필요한 String 객체 생성을 줄일 수 있다.

StringBuilder sb = new StringBuilder();
sb.append("ab");
sb.insert(1, "X");
sb.replace(0, 1, "Y"); // 시작 포함, 끝 제외
String part = sb.substring(0, 2); // 반환형 String
sb.reverse();
String result = sb.toString();
sb.setLength(0); // 내용 초기화 후 재사용

---

4. Character

char c = 'A';
char k = 'B';
 
Character.toString(c);
Character.compare(c, k); // 음수 / 0 / 양수
Character.isUpperCase(c);
Character.isLowerCase(k);
Character.isDigit(c);
Character.isAlphabetic(k);

Note

Character.isAlphabetic()은 영문 A~Z만이 아니라 유니코드상의 여러 문자도 포함한다. 영문 여부만 검사하려면 범위를 직접 비교한다.

---

5. 배열 Array와 Arrays

배열은 길이가 고정되어 있으며, 길이는 arr.length로 확인한다.

int[] scores = new int[5];
String[] names = new String[3];
 
for (int i = 0; i < scores.length; i++) {
    System.out.println(scores[i]);
}
System.out.println(Arrays.toString(scores));

메서드	설명
Arrays.fill(arr, -1)	전체 요소 초기화
Arrays.sort(arr)	오름차순 정렬
Arrays.toString(arr)	1차원 배열 출력용 문자열
Arrays.deepToString(arr2d)	중첩 배열 출력용 문자열
Arrays.copyOfRange(arr, s, e)	s 이상 e 미만 복사
Arrays.binarySearch(arr, key)	정렬된 배열에서 이진 탐색
Arrays.stream(arr).max().orElse(0)	배열 최댓값; 비어 있으면 기본값
Arrays.stream(arr).min().orElse(0)	배열 최솟값; 비어 있으면 기본값

int[] arr = {1, 3, 5, 7};
int index = Arrays.binarySearch(arr, 5); // 2
boolean exists = Arrays.binarySearch(arr, 4) >= 0; // false

binarySearch 반환값

값이 있으면 인덱스(0 이상), 없으면 **-(삽입 위치) - 1**을 반환한다. -1만 반환하는 것이 아니다. 검색 구간은 정렬되어 있어야 한다.

---

6. List와 ArrayList

길이가 변하는 데이터는 ArrayList가 편리하다. 임의 위치 삽입·삭제는 요소 이동 때문에 O(N)일 수 있다.

List<Integer> list = new ArrayList<>();
list.add(10);
list.add(20);
list.set(0, 11);
int value = list.get(0);
int size = list.size();
list.remove(0);                  // 인덱스 0 삭제
list.remove(Integer.valueOf(20)); // 값 20 삭제
list.removeIf(x -> x < 0);       // 조건을 만족하는 요소 삭제

remove() 오버로드

List<Integer>에서 remove(2)는 값 2가 아니라 인덱스 2를 삭제한다. 값으로 삭제할 땐 remove(Integer.valueOf(2)).

Collections.sort(list); // 오름차순
list.sort(Collections.reverseOrder()); // 내림차순
Collections.reverse(list); // 현재 순서 뒤집기 (정렬과 다름)

---

7. Collections 유틸리티

List<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 2, 3));
 
Collections.frequency(list, 2); // 2
Collections.sort(list);         // 이진 탐색 전 정렬
int idx = Collections.binarySearch(list, 2); // 중복 시 어느 인덱스인지는 보장 안 됨
Collections.reverse(list);      // 순서 뒤집기

역순 정렬된 리스트의 이진 탐색

Collections.binarySearch(list, key)는 자연 오름차순을 전제로 한다. 내림차순 리스트는 같은 정렬 비교자를 전달해야 한다.

list.sort(Collections.reverseOrder());
int idx = Collections.binarySearch(list, 2, Collections.reverseOrder());

---

8. 기본 자료구조

8.1 Stack — LIFO

Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.peek();
stack.pop();
stack.isEmpty();
stack.size();

• 대표 활용: 괄호 검사, 문자열 제거
• 실제 코테에서는 Deque<Integer> stack = new ArrayDeque<>();와 push/pop/peek 조합도 자주 사용한다.

8.2 Queue — FIFO

Queue<Integer> queue = new ArrayDeque<>();
queue.offer(1);
queue.peek();
queue.poll();
queue.isEmpty();
queue.size();

• 대표 활용: BFS
• poll()은 비어 있으면 null, remove()는 예외를 발생시킨다.

8.3 PriorityQueue — 힙

PriorityQueue<Integer> minHeap = new PriorityQueue<>();
PriorityQueue<Integer> maxHeap =
        new PriorityQueue<>(Collections.reverseOrder());
 
minHeap.offer(3);
minHeap.offer(1);
minHeap.peek(); // 1
minHeap.poll(); // 1

• 기본은 최소 힙. 가장 우선순위가 높은 값부터 꺼낸다.

8.4 Deque — 양방향

Deque<Integer> deque = new ArrayDeque<>();
deque.offerFirst(1);
deque.offerLast(2);
deque.peekFirst();
deque.peekLast();
deque.pollFirst();
deque.pollLast();

• 대표 활용: 양방향 큐, 스택 대체, 슬라이딩 윈도우

8.5 Set — 중복 제거

Set<Integer> set = new HashSet<>();
set.add(1);
set.contains(1);
set.remove(1);
set.size();

종류	특징
HashSet	순서 보장 없음
LinkedHashSet	삽입 순서 유지
TreeSet	정렬 순서 유지

8.6 Map — 키와 값

Map<String, Integer> map = new HashMap<>();
map.put("a", 1);
map.get("a");
map.remove("a");
map.containsKey("a");
map.containsValue(1);
 
// 빈도 카운팅
map.put("a", map.getOrDefault("a", 0) + 1);
 
// Map의 모든 value를 독립된 List로 복사
List<Integer> values = new ArrayList<>(map.values());
 
for (String key : map.keySet()) {
    System.out.println(key);
}
for (Map.Entry<String, Integer> e : map.entrySet()) {
    System.out.println(e.getKey() + ": " + e.getValue());
}

map.values()의 순서는 Map의 순회 순서를 따르므로 HashMap에서는 순서를 보장하지 않는다. 같은 value가 여러 키에 저장되어 있으면 중복도 그대로 유지된다.

8.7 주요 자료구조 시간복잡도

N은 저장된 원소의 개수다.

자료구조	주요 연산	시간복잡도	주의
배열	인덱스 조회·수정	O(1)	값 탐색은 O(N)
ArrayList	get, set	O(1)	중간 삽입·삭제와 contains는 O(N)
ArrayList	끝에 add	분할상환 O(1)	용량 확장 시 해당 연산은 O(N)
HashMap, HashSet	조회·삽입·삭제	평균 O(1)	충돌이 집중되면 최악 O(N)까지 가능
TreeMap, TreeSet	조회·삽입·삭제	O(log N)	정렬 순서를 유지할 때 사용
ArrayDeque	양 끝 삽입·삭제·조회	분할상환 O(1)	용량 확장 시 해당 연산은 O(N), 중간 값 탐색은 O(N)
PriorityQueue	offer, poll	O(log N)	peek은 O(1), 특정 값 탐색·삭제는 O(N)

Tip

코딩테스트에서는 평균 시간복잡도뿐 아니라 전체 반복 횟수도 함께 계산한다. O(N) 반복문 안에서 O(log N) 연산을 수행하면 전체는 O(N log N)이다.

---

9. 2차원 배열과 그래프 표현

9.1 배열 + 배열 (행·열 고정)

int n = 5;
int[][] graph = new int[n + 1][n + 1];

9.2 배열 + ArrayList (행 고정, 열 가변)

int n = 5;
@SuppressWarnings("unchecked")
ArrayList<Integer>[] graph = new ArrayList[n + 1];
 
for (int i = 0; i <= n; i++) {
    graph[i] = new ArrayList<>();
}
 
int[][] edges = {{1, 2}, {2, 3}};
for (int[] edge : edges) {
    graph[edge[0]].add(edge[1]);
    graph[edge[1]].add(edge[0]); // 무방향 그래프일 때만
}

Note

제네릭 배열은 직접 생성할 수 없어 배열 생성 시 컴파일러의 unchecked 경고가 발생한다. 이 예시는 경고를 억제하지만 아래 중첩 리스트 방식도 사용할 수 있다.

9.3 ArrayList + ArrayList (각 행의 원소 개수 가변)

int n = 5;
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i <= n; i++) {
    graph.add(new ArrayList<>());
}
graph.get(1).add(2);

• 행을 동적으로 추가할 수 있지만 인덱스로 접근하기 전에 해당 행을 생성해야 한다.
• 인접 리스트는 일반적으로 간선 수가 적은 그래프에 유용하다.

---

10. 정렬 Comparator

비교 함수 반환값의 부호가 원소의 앞뒤 순서를 결정한다.

비교 결과	의미
음수	a가 b보다 앞
0	두 값의 정렬상 순위가 같음
양수	b가 a보다 앞

// 권장: 뺄셈 대신 compare (정수 오버플로 방지)
Integer.compare(a, b); // 오름차순
Integer.compare(b, a); // 내림차순

Warning

(a, b) -> a - b, (a, b) -> b - a는 암기하기 쉽지만 정수 범위가 큰 경우 오버플로로 잘못 정렬될 수 있다. 또한 비교 결과 0은 기존 순서 유지 자체를 보장하는 뜻은 아니다(정렬 알고리즘의 안정성에 따라 다름).

예제: 출현 횟수 내림차순, 동률은 사전순 오름차순

입력: ["a", "b", "a", "c", "b", "a"]
출력: ["a", "b", "c"]

String[] str = {"a", "b", "a", "c", "b", "a"};
Map<String, Integer> count = new HashMap<>();
for (String s : str) {
    count.put(s, count.getOrDefault(s, 0) + 1);
}
 
List<String> result = new ArrayList<>(count.keySet());
result.sort((a, b) -> {
    int byCount = Integer.compare(count.get(b), count.get(a));
    if (byCount != 0) return byCount;
    return a.compareTo(b);
});

---

11. Lambda와 Stream

// 람다식
(a, b) -> Integer.compare(a, b)

흐름: 생성 → 중간 연산(filter/map/sorted) → 최종 연산(collect/toArray/forEach)

// Payment, getAmount(), getId()가 정의되어 있다고 가정
List<String> ids = payments.stream()
        .filter(p -> p.getAmount() >= 50000)
        .sorted(Comparator.comparing(Payment::getAmount))
        .map(Payment::getId)
        .collect(Collectors.toList());

• 스트림은 원본 컬렉션을 직접 수정하지 않는 방식으로 처리할 수 있다.
• 한 번 소비된 스트림은 재사용할 수 없다.
• sorted()는 정렬된 새 스트림을 반환하며 원본 리스트의 순서를 변경하지 않는다.

---

12. 자료형 변환 모음

배열 ↔ List

// String[] → 수정 가능한 List<String>
String[] arr = {"A", "B", "C"};
List<String> strList = new ArrayList<>(Arrays.asList(arr));
 
// List<String> → String[]
String[] arr2 = strList.toArray(new String[0]);
 
// int[] → List<Integer>
int[] intArr = {1, 4, 3, 5, 2};
List<Integer> intList = Arrays.stream(intArr)
        .boxed()
        .collect(Collectors.toList());
 
// List<Integer> → int[]
int[] intArr2 = intList.stream()
        .mapToInt(Integer::intValue)
        .toArray();
 
// List<Integer> → Integer[]
Integer[] boxedArr = intList.toArray(new Integer[0]);

Warning

Arrays.asList(intArr)는 List<Integer>가 아니라 List<int[]> 형태가 된다. 원시 타입 배열에는 Arrays.stream(intArr).boxed()를 사용한다.

기타 변환

// int[] → String[]
String[] stringNums = Arrays.stream(intArr)
        .mapToObj(String::valueOf)
        .toArray(String[]::new);
 
// String[] → 하나의 문자열
StringBuilder sb = new StringBuilder();
Arrays.stream(stringNums).forEach(sb::append);
String joined = sb.toString();
 
// 더 간단히
String joined2 = String.join("", stringNums);

---

13. 자주 헷갈리는 문법

length / size

대상	문법
배열	arr.length
문자열	str.length()
리스트	list.size()
맵	map.size()
집합	set.size()

추가 / 조회 / 삭제

구조	추가	조회	삭제
List	add(v)	get(i)	remove(i) / remove(Object)
Set	add(v)	contains(v)	remove(v)
Queue	offer(v)	peek()	poll()
Deque	offerFirst/Last(v)	peekFirst/Last()	pollFirst/Last()
Stack	push(v)	peek()	pop()
Map	put(k,v)	get(k)	remove(k)

---

14. 자료구조 선택 가이드

자료구조	핵심 특징	대표 사용
배열	고정 길이, 인덱스 접근	탐색, DP 테이블
ArrayList	가변 길이, 빠른 인덱스 접근	정렬, 값 보관
Stack / Deque	LIFO	괄호, 문자열 제거
Queue	FIFO	BFS
PriorityQueue	우선순위 순서로 꺼내기	최솟값/최댓값 반복 선택
Deque	앞뒤 삽입·삭제	슬라이딩 윈도우
HashMap	키로 빠른 조회(평균)	빈도 카운팅
HashSet	중복 제거, 빠른 포함 검사(평균)	방문 여부
TreeSet	정렬된 집합	정렬 상태 유지

---

15. 빠른 암기 카드

수학 공식 5개

• 카테고리별 최대 1개 선택: (a+1)(b+1)… - 1
• 최소공배수: a / gcd(a,b) * b (범위·부호 주의)
• 등차수열 합: n × (첫 항 + 끝 항) / 2
• 소수 판별: i × i <= n까지만 검사
• 원형 인덱스: 음수 가능 시 Math.floorMod(i, n)

Java API 바로 떠올리기

• 배열 정렬: Arrays.sort(arr)
• 정렬된 배열 검색: Arrays.binarySearch(arr, key) >= 0
• 배열 합계: Arrays.stream(arr).sum()
• 리스트 정렬: list.sort(Comparator.naturalOrder())
• 안전한 비교: Integer.compare(a, b)
• Map 카운팅: map.put(k, map.getOrDefault(k, 0) + 1)
• 배열 출력: Arrays.toString(arr)
• 중첩 배열 출력: Arrays.deepToString(arr)
• 문자열 반복 연결: StringBuilder.append()

---

학습 범위

이 문서는 Java 문법 및 API 빠른 참조용이다. BFS/DFS, 투 포인터, 이분 탐색, 누적합 등 알고리즘 풀이 패턴/템플릿은 별도 노트에서 관리한다.