Java 코딩 테스트 필수 메서드 및 알고리즘 정리

 

목차

1. 자바 필수 메서드

문자열 처리 메서드

// charAt(int index): 문자열에서 특정 인덱스의 문자 반환
String str = "Hello";
char c = str.charAt(0); // 'H'

// substring(int beginIndex, int endIndex): 부분 문자열 추출
String sub = str.substring(1, 3); // "el"

// split(String regex): 특정 구분자로 문자열 분리
String[] parts = str.split("l"); // ["He", "", "o"]

// indexOf(String str): 특정 문자열의 첫 번째 인덱스 반환
int idx = str.indexOf("e"); // 1

// toCharArray(): 문자열을 문자 배열로 변환
char[] chars = str.toCharArray();

// replace(char oldChar, char newChar): 특정 문자 치환
String replaced = str.replace('l', 'x'); // "Hexxo"

// StringBuilder 사용
StringBuilder sb = new StringBuilder("Hello");
sb.append(" World"); // "Hello World"
sb.reverse(); // "dlroW olleH"
sb.delete(0, 6); // "olleH"

배열 관련 메서드

import java.util.Arrays;

// Arrays.sort(int[] arr): 배열 오름차순 정렬
int[] arr = {5, 3, 2, 4};
Arrays.sort(arr); // [2, 3, 4, 5]

// Arrays.binarySearch(int[] arr, int key): 이진 탐색으로 키 검색
int index = Arrays.binarySearch(arr, 3); // 1

// Arrays.copyOf(int[] original, int newLength): 배열 복사
int[] copy = Arrays.copyOf(arr, arr.length);

// Arrays.equals(int[] a, int[] b): 두 배열 비교
boolean isEqual = Arrays.equals(arr, copy); // true

// Arrays.fill(int[] arr, int val): 배열 전체를 특정 값으로 초기화
Arrays.fill(arr, 0); // [0, 0, 0, 0]

// 다차원 배열 초기화
int[][] matrix = new int[3][3];
for (int[] row : matrix) {
    Arrays.fill(row, -1);
}

컬렉션 프레임워크

import java.util.*;

// List
List<Integer> list = new ArrayList<>();
list.add(1); // 요소 추가
list.get(0); // 요소 반환
list.remove(0); // 요소 삭제
list.contains(1); // 포함 여부 확인
Collections.sort(list); // 정렬

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

// Map
Map<String, Integer> map = new HashMap<>();
map.put("key", 1); // 키-값 추가
map.get("key"); // 값 반환
map.containsKey("key"); // 키 존재 여부

// PriorityQueue (우선순위 큐)
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(5);
pq.add(1);
pq.add(3);
while (!pq.isEmpty()) {
    System.out.println(pq.poll()); // 우선순위 높은 요소 반환 및 제거
}

기타 유용한 메서드

import java.lang.Math;

// Math.max(int a, int b): 두 수 중 최대값 반환
int max = Math.max(10, 20);

// Math.min(int a, int b): 두 수 중 최소값 반환
int min = Math.min(10, 20);

// Math.abs(int a): 절대값 반환
int abs = Math.abs(-10);

// Math.pow(double a, double b): a의 b 제곱 반환
double power = Math.pow(2, 3);

// Math.sqrt(double a): 제곱근 반환
double sqrt = Math.sqrt(16);

// System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length): 배열 복사
int[] src = {1, 2, 3};
int[] dest = new int[3];
System.arraycopy(src, 0, dest, 0, src.length);

// 난수 생성
Random random = new Random();
int randInt = random.nextInt(100); // 0 ~ 99

---

2. 코딩 테스트 핵심 알고리즘

정렬 알고리즘

버블 정렬 (Bubble Sort)

설명

버블 정렬은 인접한 두 요소를 비교하여 잘못된 순서라면 교환하며, 리스트를 정렬하는 단순한 알고리즘입니다.

• 시간 복잡도: O(n²)
• 공간 복잡도: O(1) (제자리 정렬)

코드

for (int i = 0; i < arr.length - 1; i++) {
    for (int j = 0; j < arr.length - i - 1; j++) {
        if (arr[j] > arr[j + 1]) {
            int temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp;
        }
    }
}

한 줄씩 설명

1. for (int i = 0; i < arr.length - 1; i++): 배열의 모든 요소를 순회하며 정렬 단계를 수행합니다.
2. for (int j = 0; j < arr.length - i - 1; j++): 현재 정렬 단계에서 남은 요소를 순회합니다.
3. if (arr[j] > arr[j + 1]): 인접한 두 요소를 비교하여 잘못된 순서일 경우 교환합니다.

단계별 동작 (예: [5, 3, 2, 4])

1. 초기 배열: [5, 3, 2, 4]
2. 첫 번째 단계: [3, 2, 4, 5]
3. 두 번째 단계: [2, 3, 4, 5]
4. 정렬 완료: [2, 3, 4, 5]

---

퀵 정렬 (Quick Sort)

설명

퀵 정렬은 분할 정복 방식을 사용하여 리스트를 정렬합니다. 피벗을 기준으로 작은 값과 큰 값을 나누고 재귀적으로 정렬합니다.

• 평균 시간 복잡도: O(n log n)
• 공간 복잡도: O(log n) (재귀 호출 스택)

코드

public static void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

private static int partition(int[] arr, int low, int high) {
    int pivot = arr[high];
    int i = (low - 1);
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return i + 1;
}

한 줄씩 설명

1. if (low < high): 정렬 구간이 유효한 경우 분할 및 재귀 호출을 진행합니다.
2. partition(arr, low, high): 피벗을 기준으로 배열을 분할합니다.
3. int pivot = arr[high]: 마지막 요소를 피벗으로 설정합니다.
4. for (int j = low; j < high; j++): 피벗보다 작은 요소를 왼쪽으로 이동시킵니다.

단계별 동작 (예: [5, 3, 2, 4])

1. 초기 배열: [5, 3, 2, 4], 피벗 = 4
2. 첫 분할: [3, 2, 4, 5]
3. 재귀 정렬: [2, 3, 4, 5]
4. 정렬 완료: [2, 3, 4, 5]

---

병합 정렬 (Merge Sort)

설명

병합 정렬은 리스트를 절반으로 나누고 각각을 재귀적으로 정렬한 뒤 병합하는 알고리즘입니다.

• 시간 복잡도: O(n log n)
• 공간 복잡도: O(n) (병합에 사용되는 임시 배열)

코드

public static void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

private static void merge(int[] arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    int[] L = new int[n1];
    int[] R = new int[n2];

    for (int i = 0; i < n1; i++) L[i] = arr[left + i];
    for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];

    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) arr[k++] = L[i++];
        else arr[k++] = R[j++];
    }

    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

한 줄씩 설명

1. if (left < right): 배열을 더 이상 나눌 수 없을 때까지 재귀적으로 분할합니다.
2. mergeSort(arr, left, mid): 왼쪽 절반을 정렬합니다.
3. mergeSort(arr, mid + 1, right): 오른쪽 절반을 정렬합니다.
4. merge(arr, left, mid, right): 정렬된 절반을 병합합니다.

단계별 동작 (예: [5, 3, 2, 4])

1. 초기 분할: [5, 3] [2, 4]
2. 재귀 정렬: [3, 5] [2, 4]
3. 병합: [2, 3, 4, 5]

---

그래프 알고리즘

깊이 우선 탐색 (DFS)

설명

DFS는 그래프에서 가능한 깊이까지 탐색한 뒤 백트래킹하며 다른 경로를 탐색하는 방법입니다.

• 시간 복잡도: O(V + E) (정점과 간선의 합)
• 구현: 재귀 또는 스택 사용.

코드

public void dfs(int node, boolean[] visited, List<List<Integer>> graph) {
    visited[node] = true;
    System.out.print(node + " ");

    for (int neighbor : graph.get(node)) {
        if (!visited[neighbor]) {
            dfs(neighbor, visited, graph);
        }
    }
}