[250326] 코딩테스트 문제 해결을 위한 단계별 접근법 (Java 8 기반)

1. 문제 이해 및 제약조건 확인

가장 중요하고 첫 번째 단계는 문제를 정확히 이해하는 것입니다.

요구사항 파악: 문제에서 무엇을 요구하는지 명확히 파악하세요. 숨겨진 조건이나 놓치기 쉬운 세부 사항까지 꼼꼼하게 읽어야 합니다.
입력과 출력 정의: 주어진 입력 형식과 기대하는 출력 형식이 무엇인지 확실히 정의해야 합니다.
- 예시: 입력이 정수 배열 nums와 정수 target이고, 출력이 nums에서 두 수를 더해 target이 되는 인덱스 쌍이라면, 이를 명확히 인지해야 합니다.
제약조건 확인 (필수!): 효율적인 알고리즘 설계를 위해 제약조건을 반드시 확인해야 합니다.
- 데이터 크기/범위: 입력 데이터의 크기 범위 (예: 배열 길이 1 <= N <= 1,000,000, 숫자의 범위 10^9 <= num <= 10^9)를 파악하여 시간 복잡도와 공간 복잡도에 대한 감을 잡아야 합니다.
- 알고리즘 선택 기준: 제약조건은 어떤 알고리즘을 선택해야 할지 판단하는 중요한 기준입니다. 예를 들어, N이 1,000,000이라면 O(N^2) 알고리즘(약 1조 번 연산)은 시간 초과가 발생할 가능성이 높으므로 O(N log N) 또는 O(N) 알고리즘을 고려해야 합니다.
특별 조건/예외 사항:
- 데이터 특성: 중복 값 허용 여부, 데이터 정렬 여부 등을 확인합니다.
- 상황 특이점: 빈 입력 (null 또는 빈 배열/리스트), 특정 값(0, 음수 등)의 존재 여부 등을 고려합니다.
질문: 이해가 되지 않거나 모호한 점은 (시험 환경이 허락한다면) 반드시 질문하여 명확히 해야 합니다. 잘못된 이해는 오답으로 직결됩니다.

2. 입출력 예시 분석

제공된 입출력 예시는 문제 이해를 돕는 최고의 가이드입니다.

과정 추적: 주어진 입력으로 어떤 과정을 거쳐 출력이 나오는지 논리적으로 따라가며 문제 해결의 힌트를 얻습니다.
경계/극단적 케이스: 단순 예시 외에 경계 조건(최소/최대값)이나 극단적인 경우(빈 배열, 모든 값이 같음 등)가 있다면 더욱 주의 깊게 분석합니다. 이는 알고리즘의 정확성 검증에 중요합니다.
논리 역추론: 출력이 나오기까지의 중간 과정이나 규칙을 생각하며 핵심 아이디어를 떠올릴 수 있습니다.
자체 예시 생성: 문제 이해를 공고히 하고 놓칠 수 있는 예외 상황을 발견하기 위해 스스로 추가 예시를 만들어 테스트해 봅니다.
- 예시: 배열에서 두 수의 합 찾기 문제에서 [3, 3], target = 6과 같은 중복 값이 있는 경우, [1, 5, 9], target = 4와 같이 해답이 없는 경우 등을 직접 만들어 봅니다.

3. 핵심 아이디어 및 알고리즘 구상

문제 해결의 '방법'을 설계하는 단계입니다.

접근 방식 구상: 문제 요구사항, 입출력 분석, 제약조건을 바탕으로 어떤 접근 방식을 사용할지 결정합니다.

알고리즘/자료구조 선택:

문제 유형에 맞는 다양한 알고리즘과 자료구조를 떠올리고 최적의 것을 선택합니다.
탐색: 깊이 우선 탐색 (DFS), 너비 우선 탐색 (BFS)
정렬된 데이터 탐색: 이분 탐색 (Binary Search)
최단 경로: 다익스트라 (Dijkstra), 벨만-포드 (Bellman-Ford), 플로이드-워셜 (Floyd-Warshall)
효율적 저장/검색: 해시 맵 (HashMap), 해시 셋 (HashSet)
순서/우선순위: 큐 (Queue), 스택 (Stack), 우선순위 큐 (PriorityQueue)

// 예시: 이분 탐색 기본 구조
int binarySearch(int[] sortedArray, int target) {
    int low = 0;
    int high = sortedArray.length - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2; // 오버플로우 방지

        if (sortedArray[mid] == target) {
            return mid; // 찾음
        } else if (sortedArray[mid] < target) {
            low = mid + 1; // 오른쪽 탐색
        } else {
            high = mid - 1; // 왼쪽 탐색
        }
    }
    return -1; // 못 찾음
}

알고리즘 설계 기법:

분할 정복 (Divide and Conquer): 문제를 작은 하위 문제로 나눠 해결 (예: 병합 정렬, 퀵 정렬)
동적 계획법 (Dynamic Programming, DP): 이전 계산 결과를 재활용하여 효율성 증대. 부분 문제가 반복될 때 유용.

// 예시: 피보나치 수열 (DP - Memoization)
int[] memo = new int[101]; // 메모이제이션 배열 (0으로 초기화)

int fibonacci(int n) {
    if (n <= 1) {
        return n;
    }
    if (memo[n] != 0) { // 이미 계산된 값이면 반환
        return memo[n];
    }
    memo[n] = fibonacci(n - 1) + fibonacci(n - 2); // 계산하고 저장
    return memo[n];
}

탐욕 알고리즘 (Greedy Algorithm): 각 단계에서 최적의 선택을 하여 전체 최적 해를 기대. 항상 최적 해를 보장하지 않으므로 주의.

// 예시: 거스름돈 문제 (Greedy - 동전 종류가 {500, 100, 50, 10} 등 배수 관계일 때)
int countCoins(int amount) {
    int[] coins = {500, 100, 50, 10};
    int count = 0;
    for (int coin : coins) {
        count += amount / coin; // 가장 큰 동전부터 최대한 사용
        amount %= coin;
    }
    return count;
}

아이디어 정리: 구상한 아이디어를 간략히 메모하거나 의사 코드 (Pseudo Code)로 작성하여 논리 흐름을 명확히 합니다. 구현 중 오류를 줄이고 시간을 절약하는 데 도움이 됩니다.

4. 시간/공간 복잡도 예측

설계한 알고리즘의 효율성을 미리 평가하는 중요한 단계입니다.

시간 복잡도 (Time Complexity):
- 입력 크기(N) 기준 **최악의 경우 (Worst Case)**를 고려하여 Big O 표기법으로 표현합니다.
- 일반적인 복잡도:
  - O(1): 상수 시간 (입력 크기와 무관)
  - O(log N): 로그 시간 (예: 이분 탐색)
  - O(N): 선형 시간 (예: 배열 순회)
  - O(N log N): 로그 선형 시간 (예: 효율적인 정렬 - 병합, 퀵)
  - O(N^2): 제곱 시간 (예: 이중 반복문)
  - O(2^N): 지수 시간 (예: 단순 재귀 조합 생성)
- 문제의 시간 제한(보통 1초 ~ 5초)과 N의 최대 크기를 비교하여 알고리즘이 적절한지 판단합니다. (일반적으로 1초에 약 1억 번의 연산 가능)
```
// O(N^2) 예시: 배열에서 모든 쌍 비교
void checkPairs(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) { // 중첩 반복문
            // arr[i]와 arr[j] 비교 로직
        }
    }
}

// O(N) 예시: 배열 합계 계산
long sumArray(int[] arr) {
    long sum = 0;
    for (int x : arr) { // 단일 반복문
        sum += x;
    }
    return sum;
}
```
공간 복잡도 (Space Complexity):
- 알고리즘 실행에 필요한 추가 메모리 사용량을 예측합니다. (자료구조 크기, 재귀 호출 스택 깊이 등)
- 문제의 메모리 제한(보통 128MB ~ 512MB)을 넘지 않는지 확인합니다.
개선 필요 시: 예측 복잡도가 제한을 초과하면, 다른 알고리즘을 고려하거나, 더 효율적인 자료구조 사용(예: 배열 탐색 대신 HashMap 사용으로 O(N) -> O(1) 평균 시간) 등으로 개선 방법을 찾습니다.

5. Java 8 기반 구현

구상한 아이디어를 실제 코드로 옮기는 단계입니다.

Java 8 기능 활용:

Stream API: 컬렉션 데이터를 간결하고 선언적으로 처리할 때 유용합니다. filter, map, reduce, collect 등 활용.

// 예시: 리스트에서 짝수만 제곱하여 새 리스트 만들기 (Stream API)
List<Integer> numbers = Arrays.asList(1, 2, 3, 4, 5);
List<Integer> squaredEvens = numbers.stream() // 스트림 생성
                                   .filter(n -> n % 2 == 0) // 짝수 필터링
                                   .map(n -> n * n)         // 제곱
                                   .collect(Collectors.toList()); // 리스트로 수집
// squaredEvens: [4, 16]

Lambda 표현식: 인터페이스의 익명 구현을 간결하게 표현 (특히 함수형 인터페이스와 함께 사용).

// 예시: 문자열 길이 기준으로 리스트 정렬 (Lambda)
List<String> names = Arrays.asList("Alice", "Bob", "Charlie", "Ed");
Collections.sort(names, (s1, s2) -> s1.length() - s2.length()); // 람다로 Comparator 구현
// names: ["Ed", "Bob", "Alice", "Charlie"]

표준 라이브러리 활용:

Java Collections Framework: ArrayList, LinkedList, HashSet, TreeSet, HashMap, TreeMap, PriorityQueue, ArrayDeque 등 문제에 맞는 자료구조를 적극 사용합니다.

// 예시: HashMap으로 숫자 빈도수 계산
int[] data = {1, 2, 3, 2, 1, 1, 4};
Map<Integer, Integer> frequencyMap = new HashMap<>();
for (int num : data) {
    frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
}
// frequencyMap: {1=3, 2=2, 3=1, 4=1}

가독성 높은 코드:
- 명확한 이름: 변수, 함수, 클래스 이름을 의미 있게 작성합니다.
- 적절한 주석: 복잡한 로직이나 핵심 아이디어를 설명하는 주석을 추가합니다.
- 일관된 스타일: 들여쓰기, 공백 등 일관된 코드 스타일을 유지합니다.
오류 주의: 문법 오류, 논리 오류가 없도록 주의하며 작성합니다. IDE의 디버깅 기능을 적극 활용하여 오류를 찾고 수정하는 연습을 합니다.

6. 엣지 케이스 테스트 및 디버깅

작성된 코드의 정확성을 철저히 검증하는 마지막 단계입니다.

다양한 테스트 케이스:

문제에서 제공된 예시 입력은 기본입니다.
*엣지 케이스 (Edge Cases)**를 직접 만들어 테스트합니다.
- 빈 입력: null, 빈 배열/리스트 ([])
- 최소/최대 경계: 제약조건의 최소/최대값 (예: N=1, N=최대값)
- 특이 값: 0, 음수, 매우 큰 값
- 모든 요소 동일: [5, 5, 5]
- 정렬/역정렬: [1, 2, 3], [3, 2, 1]
- 해답 없는 경우

// 예시: 엣지 케이스 테스트 (가상 함수 `solve`)
// assertEquals(expected, actual) 형태의 테스트 함수가 있다고 가정

// 기본 테스트
assertEquals(expectedOutput1, solve(normalInput1));

// 엣지 케이스 테스트
assertEquals(emptyResult, solve(new int[]{})); // 빈 배열
assertEquals(singleElementResult, solve(new int[]{5})); // 요소 1개
assertEquals(allSameResult, solve(new int[]{3, 3, 3, 3})); // 모든 요소 동일
assertEquals(minMaxResult, solve(new int[]{Integer.MIN_VALUE, Integer.MAX_VALUE})); // 최소/최대값
assertEquals(noAnswerResult, solve(inputWithNoAnswer)); // 해답 없는 경우

디버깅:
- 테스트 중 오류 발생 시, 디버깅 도구(브레이크포인트, 스텝 실행, 변수 값 확인 등)를 사용하여 원인을 정확히 파악하고 수정합니다.
- System.out.println을 이용한 중간 값 확인도 간단한 디버깅 방법입니다.
코드 수정 후 재검증: 코드를 수정했다면, 해당 수정이 다른 부분에 **부작용(Side Effect)**을 일으키지 않는지 관련 테스트 케이스로 다시 확인합니다.

이러한 단계별 접근법을 꾸준히 연습하고 숙달한다면, 코딩테스트에서 더욱 침착하고 효율적으로 문제를 해결하여 좋은 결과를 얻으실 수 있을 것입니다. Java 8의 강력한 기능과 체계적인 문제 해결 전략을 활용하여 목표를 이루시기를 응원합니다!

'Learning > TIL' 카테고리의 다른 글

Ollama on Rancher Desktop (Windows): Docker 연결 및 메모리 부족 오류 트러블슈팅 (0)	2025.05.20
[250326] 안티패턴 (1)	2025.03.26
[250325] Aiven & 프로젝트 (1)	2025.03.25
[250325] 자격증 (0)	2025.03.25
도커(Docker)? (0)	2025.03.13