JavaScript로 정렬된 배열에서 첫 번째 고유 요소 찾기

문제 정의

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

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

우리가 작성해야 할 것은 이러한 배열을 입력받아 딱 한 번만 등장하는 첫 번째 숫자를 반환하는 JavaScript 함수입니다.

만약 배열 안에 그러한 숫자가 존재하지 않는다면 false를 반환해야 합니다.

위 배열의 경우 출력 결과는 6이어야 합니다. 2, 3, 5는 각각 두 번 이상 반복되어 등장하지만, 6은 가장 먼저 한 번만 나타나는 값이기 때문입니다.

예제 코드

이 문제를 해결하는 코드는 다음과 같습니다.

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));

코드 동작 원리

이 알고리즘의 핵심은 appeared라는 불리언 플래그 변수입니다.

appeared = true인 경우: 현재 요소가 반복 그룹에 속해 있음을 의미합니다. 이때 다음 요소(arr[i+1])와 현재 요소가 달라지면 반복이 끝난 것이므로 플래그를 false로 되돌립니다.
appeared = false인 경우: 새로운 값 그룹을 만났음을 의미합니다. 바로 다음 요소와 값이 같다면 반복이 시작된 것이므로 플래그를 true로 설정하고 건너뜁니다. 다음 요소와 값이 다르다면 해당 요소가 한 번만 등장한 첫 번째 숫자이므로 즉시 반환합니다.

배열이 이미 정렬되어 있기 때문에 같은 값들은 항상 인접해 있다는 점을 활용한 방식입니다. 덕분에 해시 맵이나 추가 자료구조 없이도 문제를 해결할 수 있습니다.

성능 분석

시간 복잡도: O(n) — 배열을 한 번만 순회하면 됩니다.
공간 복잡도: O(1) — 플래그 변수 하나만 사용하므로 추가 메모리가 거의 필요하지 않습니다.

출력 결과

콘솔에 출력되는 결과는 다음과 같습니다.