이번 글에서는 정수 배열을 입력받아, 배열 안에서 딱 한 번만 등장하는 숫자 중 가장 큰 값을 반환하는 JavaScript 함수를 작성해 보겠습니다.
문제 정의
함수는 정수 배열을 첫 번째이자 유일한 인자로 받습니다. 이후 배열을 순회하면서 오직 한 번만 나타난 숫자들 중 최댓값을 골라 반환해야 합니다.
만약 배열에 고유한(중복되지 않은) 숫자가 하나도 없다면 -1을 반환하면 됩니다.
추가로 문제에서는 다음과 같은 조건을 제시합니다. 배열의 모든 요소는 0보다 크고 100보다 작거나 같다는 것입니다.
0 < arr[i] <= 100
즉, 배열의 모든 인덱스 i에 대해 위 범위가 항상 성립합니다.
예시
입력 배열이 다음과 같다고 가정해 봅시다.
const arr = [35, 37, 33, 39, 34, 39, 38, 31];
여기서 한 번만 등장하는 숫자는 35, 37, 33, 34, 38, 31이며, 그중 가장 큰 값은 38입니다. 따라서 출력은 다음과 같아야 합니다.
const output = 38;
접근 방법
배열의 모든 요소가 100 이하의 양수라는 조건 덕분에 아주 효율적인 풀이가 가능합니다. 길이가 100인 빈도수(frequency) 배열을 만들어 원본 배열에 등장하는 각 숫자의 개수를 기록하고, 이후 큰 숫자부터 역순으로 탐색하면서 빈도수가 정확히 1인 첫 번째 숫자를 찾으면 됩니다.
이 방식은 시간 복잡도 O(n + k)(n은 배열 길이, k는 상숫값 100), 공간 복잡도 O(k)로 매우 효율적입니다.
구현 코드
전체 코드는 다음과 같습니다.
const arr = [35, 37, 33, 39, 34, 39, 38, 31];
const pickGreatestUnique = (arr = [], bound = 100) => {
// 각 숫자의 등장 횟수를 저장할 배열 생성
const map = Array(bound).fill(0);
// 원본 배열을 순회하며 빈도수 기록
for (let i = 0; i < arr.length; i++) {
const num = arr[i];
map[num - 1]++;
}
// 큰 숫자부터 역순으로 탐색하여 고유한 숫자 확인
for (let j = bound - 1; j >= 0; j--) {
const frequency = map[j];
if (frequency === 1) {
return j + 1;
}
}
// 고유한 숫자가 없는 경우 -1 반환
return -1;
};
console.log(pickGreatestUnique(arr));실행 결과
콘솔에 출력되는 결과는 다음과 같습니다.
38
코드 설명
- map[num - 1]++: 숫자 값을 그대로 인덱스로 사용하기 위해 1을 빼서 저장합니다. 예를 들어 숫자 35는 인덱스 34에 기록됩니다.
- 역순 탐색: 인덱스 99부터 0까지 거꾸로 확인하므로, 빈도수가 1인 숫자를 발견하는 즉시 그것이 곧 '가장 큰 고유 숫자'가 됩니다.
- return j + 1: 저장 시 1을 뺐기 때문에 실제 숫자 값을 되돌려 줄 때는 다시 1을 더해 줍니다.
이처럼 제약 조건(요소 값의 범위)을 잘 활용하면 해시맵 없이도 간단하고 빠르게 문제를 해결할 수 있습니다.