안녕하세요! 오늘은 자바스크립트 코딩테스트의 중요한 주제 중 하나인 ‘오큰수 구하기’에 대해 알아보겠습니다. 이 문제는 배열에서 각 원소의 오큰수를 구하는 것으로, 효율적인 알고리즘 설계가 필요합니다. 이번 글에서는 문제 설명, 접근 방법, 알고리즘 구현까지 상세히 다룰 예정입니다.
문제 설명
주어진 배열에서 각 원소에 대해 그 원소 오른쪽에 위치한 더 큰 수 중 가장 먼저 나타나는 수를 찾는 문제입니다. 만약 그런 수가 없다면 -1을 반환합니다.
예제
- 입력:
[2, 3, 3, 5, 4, 9, 6]
출력:[3, 5, 5, 9, 9, -1, -1] - 입력:
[1, 2, 3, 4]
출력:[2, 3, 4, -1] - 입력:
[5, 4, 3, 2, 1]
출력:[-1, -1, -1, -1, -1]
문제 접근 방법
이 문제를 해결하기 위한 접근 방식은 두 가지가 있습니다. 첫 번째는 단순한 이중 반복문을 사용하는 방법이며, 두 번째는 스택을 이용하는 방법입니다. 두 번째 방법이 시간 복잡도 면에서 효율적입니다.
1. 이중 반복문 접근
각 원소에 대해 오른쪽에 있는 원소들을 모두 확인하여 오큰수를 찾는 방법입니다. 이 방법은 구현이 쉽지만, 시간 복잡도가 O(N^2)로 비효율적입니다.
function findNextGreaterElements(arr) {
const result = [];
const n = arr.length;
for (let i = 0; i < n; i++) {
let found = false;
for (let j = i + 1; j < n; j++) {
if (arr[j] > arr[i]) {
result[i] = arr[j];
found = true;
break;
}
}
if (!found) {
result[i] = -1;
}
}
return result;
}
// 예시 사용
console.log(findNextGreaterElements([2, 3, 3, 5, 4, 9, 6]));
// 출력: [3, 5, 5, 9, 9, -1, -1]
2. 스택을 이용한 접근
스택을 활용하여 문제를 해결하는 방법입니다. 이 방법은 각 원소에 대해 스택을 사용하여 처리하므로 시간이 O(N) 이며, 공간 복잡도는 O(N)입니다.
알고리즘은 다음과 같습니다:
- 스택을 초기화합니다.
- 각 원소에 대해 반복합니다.
- 스택의 최상단 원소가 현재 원소보다 작으면, 스택에서 팝하여 그 원소의 오큰수를 현재 원소로 설정합니다.
- 현재 원소의 인덱스를 스택에 푸시합니다.
- 반복이 끝나면 스택에 남아 있는 원소들은 -1로 설정합니다.
function findNextGreaterElements(arr) {
const result = new Array(arr.length).fill(-1);
const stack = [];
for (let i = 0; i < arr.length; i++) {
while (stack.length > 0 && arr[stack[stack.length - 1]] < arr[i]) {
const index = stack.pop();
result[index] = arr[i];
}
stack.push(i);
}
return result;
}
// 예시 사용
console.log(findNextGreaterElements([2, 3, 3, 5, 4, 9, 6]));
// 출력: [3, 5, 5, 9, 9, -1, -1]
결론
오큰수 구하기 문제는 배열의 원소를 기반으로 하여 나중에 나타나는 큰 수를 찾는 과정을 통해 알고리즘 문제 해결 능력을 기를 수 있는 좋은 문제입니다. 반복문을 활용한 단순한 방법과 스택을 이용한 효율적인 방법 모두를 이해하고 적용하는 것이 중요합니다. 앞으로도 이러한 문제들을 통해 더 많은 알고리즘과 자료구조를 공부하길 바랍니다!
참고 자료
- 자료구조와 알고리즘: 강의 및 책
- 온라인 코딩 테스트 플랫폼 (예: LeetCode, HackerRank)
- 자바스크립트 공식 문서