자바스크립트 코딩테스트 강좌, 원하는 정수 찾기

문제 설명

주어진 배열에서 특정 정수를 찾아 해당 정수의 인덱스를 반환하는 함수를 구현하세요. 만약 배열에 특정 정수가 없다면 -1을 반환해야 합니다.

함수 정의는 다음과 같습니다:

function findInteger(arr: number[], target: number): number

입력:

• arr: 탐색할 정수 배열 (0 ≤ arr.length ≤ 10^5)
• target: 찾고자 하는 정수 (-10^9 ≤ target ≤ 10^9)

출력:

• target이 arr에 존재할 경우, target의 인덱스 값을 반환
• target이 arr에 존재하지 않을 경우, -1을 반환

문제 분석

문제를 이해하기 위해서는 입력 배열에 대한 몇 가지 예시를 살펴보는 것이 좋습니다.

• 예시 1: findInteger([1, 2, 3, 4, 5], 3) → 출력: 2 (3의 인덱스)
• 예시 2: findInteger([10, 20, 30], 25) → 출력: -1 (25는 배열에 없음)
• 예시 3: findInteger([1, 2, 3, 4, 5], 5) → 출력: 4 (5의 인덱스)

이 문제는 정수 배열에서 특정 정수를 찾는 것이기 때문에, 배열을 순회하면서 해당 정수를 찾는 방법이 가장 일반적일 것입니다. 그러나 최악의 경우, 배열의 길이가 100,000일 수 있으므로, 효율적인 해결책이 필요합니다.

해결 방안

이 문제를 해결하기 위해 두 가지 접근법을 고려해볼 수 있습니다:

• 선형 탐색 (O(n))
• 이진 탐색 (정렬된 배열일 경우, O(log n))

선형 탐색은 배열의 모든 요소를 순회하며 비교하는 방법입니다. 이 방법은 구현이 간단하지만, 최악의 경우 O(n) 시간이 소요됩니다. 하지만 이진 탐색은 주어진 배열이 정렬되어 있는 경우에만 가능한 방법입니다. 따라서 이 문제의 경우 배열이 정렬되어 있지 않을 가능성을 배제할 수 없습니다. 이에 따라 선형 탐색 방법을 선택해 보겠습니다.

구현

아래는 함수의 구체적인 구현 예제입니다:

function findInteger(arr, target) {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) {
            return i; // 타겟을 찾았을 때 인덱스를 반환
        }
    }
    return -1; // 타겟이 없으면 -1 반환
}
            

위 코드는 다음과 같은 과정을 거칩니다:

1. 주어진 배열 arr을 for 루프를 통해 순회합니다.
2. 각 요소 arr[i]을 target과 비교합니다.
3. 일치하는 경우 해당 인덱스 i를 반환합니다.
4. 배열의 끝까지 도달했음에도 타겟을 찾지 못했을 경우, -1을 반환합니다.

이제 이 함수를 테스트해보겠습니다:

console.log(findInteger([1, 2, 3, 4, 5], 3)); // 2
console.log(findInteger([10, 20, 30], 25)); // -1
console.log(findInteger([1, 2, 3, 4, 5], 5)); // 4
            

시간 복잡도 분석

위의 알고리즘의 시간 복잡도는 O(n)입니다. 배열의 길이에 따라 탐색해야 하는 최대 횟수는 배열의 길이에 비례하기 때문입니다. 최악의 경우에는 배열의 모든 요소를 비교해야 할 수 있습니다.

공간 복잡도는 O(1)로, 추가적인 데이터 구조를 사용하지 않고 원래의 배열만을 활용하기 때문에 메모리 사용량이 일정합니다.

결론

이번 강좌에서는 자바스크립트를 이용해 ‘원하는 정수 찾기’ 문제를 해결하는 방법에 대해 살펴보았습니다. 문제를 분석하고, 적합한 알고리즘을 선택하여 구현하는 과정을 통해 코딩 테스트를 준비하는 데 중요한 기술을 연습할 수 있었습니다. 이와 같은 과정을 반복하면서 다양한 문제를 접하고 해결해 나간다면, 충분히 실력을 향상시킬 수 있을 것입니다. 앞으로도 많은 알고리즘 문제를 풀어보며 자신만의 해법을 찾아보시기 바랍니다.