[코딩 테스트] Java 빠르게 준비하기

1. 배열(Array)과 리스트(ArrayList)

코딩 테스트의 80%는 배열 조작입니다. Java 배열은 크기가 고정되므로, 가변적인 처리는 ArrayList를 사용합니다.

핵심 포인트

• 배열 길이: arr.length (괄호 없음)
• 리스트 크기: list.size() (메서드)
• 배열 초기화: Arrays.fill(arr, -1); (특정 값으로 채우기)
• 배열 출력: Arrays.toString(arr); (디버깅용)

샘플 코드

Java

 

import java.util.*;

public class ArraySample {
    public static void main(String[] args) {
        // 1. 배열 선언 및 초기화
        int[] arr = {1, 2, 3, 4, 5};
        
        // 2. 가변 리스트 (ArrayList)
        List<Integer> list = new ArrayList<>();
        list.add(10); // 추가
        list.get(0);  // 접근
        
        // 3. 배열 <-> 리스트 변환 (Java 21 방식)
        List<Integer> listFromArr = Arrays.stream(arr).boxed().toList();
        
        // 4. 리스트의 마지막 요소 가져오기 (Java 21 Sequenced Collections)
        int lastElement = listFromArr.getLast(); 
        int firstElement = listFromArr.getFirst();
    }
}

---

2. 순회 (Iteration) 패턴

로직 구현의 핵심은 "어떻게 루프를 돌릴 것인가"입니다.

핵심 패턴

• 일반 For문: 인덱스가 필요할 때 (예: i, i+1 비교)
• 향상된 For문 (For-each): 단순 값 순회
• 역순 순회: 뒤에서부터 처리해야 할 때 (예: 스택 문제)

샘플 코드

Java

 

// 1. 기본 순회
for (int i = 0; i < arr.length; i++) {
    // arr[i] 로직 처리
}

// 2. 역순 순회 (N-1부터 0까지)
for (int i = arr.length - 1; i >= 0; i--) {
    // 뒤에서부터 체크
}

// 3. 2차원 배열 순회 (좌표 문제)
int[][] matrix = new int[3][3];
for (int r = 0; r < matrix.length; r++) {
    for (int c = 0; c < matrix[r].length; c++) {
        // matrix[r][c] 접근
    }
}

---

3. Map & Set (조회 및 카운팅)

Python의 dict와 set입니다. **시간 복잡도 $O(1)$**을 보장하기 위해 필수적입니다.

핵심 포인트

• HashMap: 빈도수 계산, ID-값 매칭
• HashSet: 중복 제거, 존재 여부 확인 (contains)
• Map 갱신 팁: map.merge(key, 1, Integer::sum) - 카운팅할 때 매우 편리함

샘플 코드

Java

 

// 1. 빈도수 세기 (카운팅)
Map<String, Integer> map = new HashMap<>();
String[] fruits = {"apple", "banana", "apple"};

for (String f : fruits) {
    // Java 8+ 방식: 있으면 +1, 없으면 1 넣기
    map.merge(f, 1, Integer::sum);
}

// 2. 존재 여부 체크
Set<Integer> set = new HashSet<>();
set.add(1);
if (set.contains(1)) { // O(1)
    // 로직 실행
}

---

4. Stack & Queue (Deque 활용)

괄호 검사나 BFS(너비 우선 탐색) 문제에서 필수입니다. Java에서는 ArrayDeque 하나로 스택과 큐를 모두 처리합니다.

핵심 메서드

• Stack: push(), pop(), peek()
• Queue: offer(), poll(), peek()

샘플 코드

Java

 

// ArrayDeque가 Stack 클래스보다 훨씬 빠릅니다.
Deque<Integer> stack = new ArrayDeque<>();

// 스택으로 사용
stack.push(1); 
stack.push(2);
int val = stack.pop(); // 2

// 큐로 사용
Deque<Integer> queue = new ArrayDeque<>();
queue.offer(1);
queue.offer(2);
int top = queue.poll(); // 1

---

5. 정렬 (Sorting)

정렬은 문제를 단순화하는 가장 강력한 무기입니다 ($O(N \log N)$).

샘플 코드

Java

 

// 1. 오름차순
Arrays.sort(arr);

// 2. 내림차순 (Primitive 배열은 복잡하므로 boxed 처리 권장)
Integer[] arr2 = {3, 1, 4};
Arrays.sort(arr2, Collections.reverseOrder());

// 3. 객체 정렬 (람다식)
List<int[]> intervals = new ArrayList<>();
intervals.sort((a, b) -> a[0] - b[0]); // 첫 번째 원소 기준 오름차순

---

6. 로직 구현 시 주의할 점 (Java 특성)

1. 문자열 비교: ==가 아니라 **str1.equals(str2)**를 사용하세요. (매우 중요)
2. 값 복사: 배열을 복사할 때는 int[] newArr = arr.clone(); 혹은 Arrays.copyOf()를 쓰세요. 단순히 newArr = arr라고 하면 주소만 복사됩니다.
3. 최대/최소값 초기화:
   • int max = Integer.MIN_VALUE;
   • int min = Integer.MAX_VALUE;
4. 입출력 최적화: 데이터가 10만 개 이상이면 Scanner 대신 BufferedReader를 사용해야 시간 초과를 면할 수 있습니다.

---

🚀 코딩 테스트 시작 전 '준비 코드' (Template)

Java로 문제를 풀 때 가장 기본이 되는 클래스 구조입니다.

Java

 

import java.util.*;

class Solution {
    public int solution(int[] A) {
        // 1. 예외 처리 (배열이 비었을 때 등)
        if (A.length == 0) return 0;
        
        // 2. 필요한 자료구조 선언
        Map<Integer, Integer> map = new HashMap<>();
        
        // 3. 로직 구현 (루프)
        for (int x : A) {
            // ... 로직
        }
        
        return 0; // 결과 반환
    }
}

이제 이 기본 도구들을 가지고 실제 Codility 문제를 풀어보실 준비가 되었습니다. 혹시 특정 알고리즘(예: 소수 판별, 이진 탐색)의 구현 코드도 필요하신가요?

 

-----

1. 소수 판별 및 약수 구하기 ($O(\sqrt{N})$)

단순히 $N$까지 루프를 돌면 시간 초과가 납니다. 반드시 제곱근까지만 돌아야 효율성 테스트를 통과합니다.

Java

 

import java.util.*;

public class MathUtils {
    // 1. 소수 판별 (True/False)
    public boolean isPrime(int n) {
        if (n < 2) return false;
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0) return false;
        }
        return true;
    }

    // 2. 모든 약수 구하기 (List 반환)
    public List<Integer> getDivisors(int n) {
        List<Integer> list = new ArrayList<>();
        for (int i = 1; i * i <= n; i++) {
            if (n % i == 0) {
                list.add(i);
                if (i != n / i) list.add(n / i); // 제곱근이 아닐 때만 짝꿍 약수 추가
            }
        }
        Collections.sort(list); // 정렬해서 반환
        return list;
    }
}

---

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

유클리드 호제법을 이용하면 재귀 단 세 줄로 해결됩니다.

Java

 

public class GCDUtils {
    // 최대공약수 (Greatest Common Divisor)
    public int gcd(int a, int b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }

    // 최소공배수 (Least Common Multiple)
    public int lcm(int a, int b) {
        // (a * b) / gcd(a, b) 공식 활용
        // 주의: 곱셈 시 오버플로우 방지를 위해 순서 조절 가능
        return (a / gcd(a, b)) * b;
    }
}

---

3. 이진 탐색 (Binary Search)

정렬된 배열에서 특정 값을 찾거나, "최적의 정답"을 찾을 때(Parametric Search) 사용합니다.

Java

 

public class SearchUtils {
    public int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;

        while (left <= right) {
            // (left + right) / 2 보다 안전한 방식 (오버플로우 방지)
            int mid = left + (right - left) / 2;

            if (arr[mid] == target) return mid;
            if (arr[mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        return -1; // 못 찾았을 때
    }
}

---

4. 누적 합 (Prefix Sum) - 안전한 인덱스 관리

앞서 parallelPrefix를 소개했지만, 실제 문제에서는 인덱스 0을 비워두는 방식이 P[end] - P[start-1] 계산 시 예외 처리 없이 깔끔합니다.

Java

 

public class PrefixSum {
    public void solution(int[] A) {
        int n = A.length;
        // 1번 인덱스부터 합계를 저장 (n+1 크기)
        long[] P = new long[n + 1];
        
        for (int i = 1; i <= n; i++) {
            P[i] = P[i - 1] + A[i - 1];
        }

        // 구간 [start, end]의 합 (0-based 기준)
        // 예: 1번부터 3번까지의 합 -> P[4] - P[1]
        // long sum = P[end + 1] - P[start];
    }
}