기초 개념

• 자료구조: 배열
• 알고리즘: 이진 탐색, 양방향 포인터(투포인터)

주요 오류 피하기 팁

• 변수의 활용을 최대한 활용하고, 목적에 맞게 명확하게 정의하세요.
• 조건 비교 연산자(==, !=)의 논리는 항상 명확히 처리하세요.
• 배열 인덱스 접근 시 범위를 초과하지 않도록 주의하세요. 특히 반복문의 종료 조건을 신중히 설정해야 합니다.

704. 이진 탐색 (Binary Search)

문제 링크 | 해설 | 동영상 강의

접근 전략

• 왼쪽 경계(left)와 오른쪽 경계(right)를 초기화합니다.
• 반복문 내에서 중간 위치(mid)를 계산하고, 목표 값과 비교합니다.
• 목표 값이 중간 값보다 작으면 왼쪽 반만 검사 → right = mid - 1.
• 목표 값이 중간 값보다 크면 오른쪽 반만 검사 → left = mid + 1.
• 값이 일치하면 해당 인덱스(mid)를 반환합니다.
• 반복 종료 후도 찾지 못했으면 -1을 반환합니다.

코드 구현

public class BinarySearchExample {
    public static void main(String[] args) {
        int[] numbers = {-1, 0, 3, 5, 9, 12};
        int targetValue = 9;
        int resultIndex = findPosition(numbers, targetValue);
        System.out.println("결과 인덱스: " + resultIndex);
    }

    public static int findPosition(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;

        while (left <= right) {
            int middle = (left + right) / 2;
            if (target < arr[middle]) {
                right = middle - 1;
            } else if (target > arr[middle]) {
                left = middle + 1;
            } else {
                return middle;
            }
        }
        return -1;
    }
}

27. 요소 제거 (Remove Element)

문제 링크 | 해설 | 동영상 강의

핵심 아이디어

• 두 개의 포인터를 사용합니다:
  • fastPointer: 전체 배열을 순회하며 값이 제거 대상이 아닌 항목을 찾아냅니다.
  • slowPointer: 새로운 배열의 위치를 추적하며, 유효한 값을 저장합니다.
• 각 단계에서 fastPointer가 가리키는 값이 삭제 대상과 다르면, 그 값을 slowPointer 위치에 복사하고, slowPointer를 한 칸 증가시킵니다.
• 최종적으로 slowPointer의 값은 새 배열의 길이입니다.

코드 예시

public class ElementRemover {
    public static void main(String[] args) {
        int[] data = {3, 2, 2, 3};
        int removeValue = 3;
        int newSize = removeTarget(data, removeValue);
        System.out.println("새로운 길이: " + newSize);
    }

    public static int removeTarget(int[] array, int value) {
        int writeIndex = 0;

        for (int readIndex = 0; readIndex < array.length; readIndex++) {
            if (array[readIndex] != value) {
                array[writeIndex] = array[readIndex];
                writeIndex++;
            }
        }

        return writeIndex;
    }
}