Computer >> 컴퓨터 >  >> 프로그래밍 >> JavaScript

정렬된 배열에서 한 번만 나타나는 첫 번째 요소 찾기 - JavaScript

정렬된 배열에서 딱 한 번만 등장하는 숫자를 찾는 것은 코딩 테스트나 실무에서 자주 마주치는 문제입니다. 이번 글에서는 JavaScript로 이 문제를 효율적으로 해결하는 방법을 살펴보겠습니다.

문제 정의

다음과 같이 오름차순으로 정렬된 숫자 배열이 있다고 가정해 보겠습니다.

const arr = [2, 2, 3, 3, 3, 5, 5, 6, 7, 8, 9];

여기서 요구되는 작업은 다음과 같습니다.

  • 배열 안에서 단 한 번만 나타나는 첫 번째 숫자를 찾아 반환합니다.
  • 그런 숫자가 존재하지 않으면 false를 반환합니다.

위 예시 배열에서 처음 두 번(2, 3, 5)은 모두 반복되어 나타나고, 그중 처음으로 한 번만 등장하는 숫자는 6입니다. 따라서 기대 출력값은 다음과 같습니다.

6

해결 접근 방식

배열이 이미 정렬되어 있기 때문에, 같은 값들은 항상 서로 인접해 있습니다. 이 특성을 활용하면 해시 맵 같은 추가 자료구조 없이도 선형 탐색으로 문제를 해결할 수 있습니다.

핵심 아이디어는 다음과 같습니다.

  1. 현재 요소가 바로 앞 요소와 같다면, 중복 그룹에 속해 있는 것이므로 플래그(appeared)를 true로 설정합니다.
  2. 플래그가 true인 상태에서 현재 요소가 다음 요소와 다르다면, 중복 그룹이 끝난 것이므로 플래그를 다시 false로 초기화합니다.
  3. 플래그가 false이면서 다음 요소와 값이 다르다면, 해당 요소는 중복 없이 단독로 나타난 숫자이므로 즉시 반환합니다.

이 방식의 시간 복잡도는 O(n), 공간 복잡도는 O(1)로 매우 효율적입니다.

구현 코드

위 로직을 화살표 함수로 구현한 코드는 다음과 같습니다.

const arr = [2, 2, 3, 3, 3, 5, 5, 6, 7, 8, 9];

const firstNonDuplicate = arr => {
    let appeared = false;
    for(let i = 0; i < arr.length; i++){
        if(appeared){
            // 중복 그룹 진행 중: 다음 요소가 달라지면 그룹 종료
            if(arr[i+1] !== arr[i]){
                appeared = false;
            }
        }else{
            // 새 그룹 시작 여부 확인
            if(arr[i+1] === arr[i]){
                appeared = true;
                continue;
            }
            // 중복 없이 단독로 나타난 첫 숫자 반환
            return arr[i];
        }
    }
    // 한 번만 나타나는 숫자가 없는 경우
    return false;
};

console.log(firstNonDuplicate(arr));

실행 결과

위 코드를 실행하면 콘솔에 다음과 같은 결과가 출력됩니다.

6

코드 동작 살펴보기

예제 배열 [2, 2, 3, 3, 3, 5, 5, 6, 7, 8, 9]를 기준으로 흐름을 추적해 보면 다음과 같습니다.

  • 인덱스 0~1: 2가 연속되므로 appeared가 true가 됩니다.
  • 인덱스 2에서 값이 3으로 바뀌며 중복 그룹이 끝나고, 곧바로 3의 중복 그룹이 시작됩니다.
  • 인덱스 4~5: 3 그룹이 끝나고 5 그룹이 시작됩니다.
  • 인덱스 7: 5 그룹이 끝나고, 현재 값 6은 다음 값 7과 다르며 이전에도 중복이 아니었으므로 6이 즉시 반환됩니다.

마무리

정렬된 배열이라는 전제 조건을 활용하면, 불필요한 메모리 사용 없이 한 번의 순회만으로 답을 찾을 수 있습니다. 만약 배열이 정렬되어 있지 않다면 Map이나 객체를 사용해 각 숫자의 등장 횟수를 센 뒤, 첫 번째로 등장 횟수가 1인 숫자를 찾는 방식으로 확장할 수 있습니다. 상황에 맞는 알고리즘을 선택하는 것이 중요합니다.