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

문제 상황

알고리즘 문제를 풀다 보면 정렬된 배열에서 중복되지 않은 값을 효율적으로 찾아야 하는 경우가 자주 있습니다. 예를 들어 다음과 같이 오름차순으로 정렬된 숫자 배열이 있다고 가정해 보겠습니다.

const arr = [32, 32, 63, 63, 63, 75, 75, 86, 87, 88, 89];

여기서 우리가 해결해야 할 과제는 다음과 같습니다.

배열을 인자로 받아 첫 번째 고유한(중복 없이 한 번만 등장하는) 숫자를 반환하는 JavaScript 함수를 작성한다.
만약 고유한 숫자가 하나도 존재하지 않는다면 false를 반환한다.

위 예제 배열의 경우 32, 63, 75는 모두 두 번 이상 등장하지만, 86부터는 각각 한 번씩만 등장합니다. 따라서 이 배열에 대한 정답은 86입니다.

해결 코드

배열이 이미 정렬되어 있다는 점을 활용하면 인접한 요소끼리만 비교하면 되므로, 시간 복잡도 O(n)으로 문제를 해결할 수 있습니다.

const arr = [32, 32, 63, 63, 63, 75, 75, 86, 87, 88, 89];

const firstUnique = 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(firstUnique(arr));

코드 동작 원리

이 알고리즘의 핵심은 appeared라는 불리언 플래그입니다. 동작 과정을 단계별로 살펴보면 다음과 같습니다.

플래그 초기화: appeared 변수를 false로 설정하여, 현재 위치의 값이 앞선 요소와 중복되었는지 여부를 추적합니다.
중복 구간 처리: arr[i]와 arr[i+1]이 같으면 appeared를 true로 만들고 continue로 건너뜁니다. 이렇게 하면 중복 그룹 내부의 요소들은 결과 후보에서 제외됩니다.
중복 종료 감지: appeared가 true인 상태에서 다음 요소가 현재 요소와 달라지면, 중복 그룹이 끝난 것이므로 플래그를 다시 false로 되돌립니다.
고유 값 반환: 플래그가 false인 상태에서 다음 요소와 값이 다르다면, 해당 값은 한 번만 등장한 것이므로 즉시 반환합니다.

실행 결과

위 코드를 실행하면 콘솔에 다음과 같은 출력이 나타납니다.

마무리 및 대안 접근법

정렬된 배열이라는 전제 조건 덕분에 해시 맵이나 추가 메모리 없이도 선형 시간 안에 답을 찾을 수 있었습니다. 만약 배열이 정렬되어 있지 않다면, Map 객체나 객체 리터럴을 사용해 각 값의 등장 횟수를 먼저 세고, 이후 배열을 순회하며 등장 횟수가 1인 첫 번째 값을 찾는 방식으로 확장할 수 있습니다. 또한 모든 요소가 중복인 경우(예: [5, 5, 5])에는 반복문이 종료된 후 false를 반환하도록 설계되어 있어, 예외 상황도 안전하게 처리합니다.