코딩테스트에서 주어진 배열의 다음 큰 수(오큰수)를 찾는 문제는 자주 출제되는 알고리즘 문제 중 하나입니다. 이 글에서는 오큰수를 찾는 문제를 정의하고, 이를 해결하기 위한 다양한 접근 방법 및 효율적인 알고리즘을 설명하겠습니다. 또한 자바로 구현 방법을 단계별로 설명하며, 구현 후에는 시간 복잡도 및 공간 복잡도에 대해서도 논의할 것입니다.
문제 정의
주어진 정수 배열에서 각 원소에 대해 그 원소보다 큰 수 중에 가장 먼저 나오는 수를 ‘오큰수’라고 정의합니다. 만약 오큰수가 존재하지 않는 경우 해당 원소에는 -1을 배치해야 합니다.
문제 예시
입력: [2, 1, 3, 2, 5] 출력: [3, 3, 5, 5, -1]
문제 분석
이 문제를 해결하기 위한 전통적인 방법은 이중 반복문을 사용하는 것입니다. 그러나 이 방법은 시간 복잡도가 O(N^2)으로 비효율적입니다. 따라서 더 효율적인 방법을 찾아야 합니다.
효율적인 접근 방법: 스택을 활용한 O(N) 해법
이 문제를 해결하기 위해 스택 자료구조를 활용할 수 있습니다. 아래는 스택을 사용한 오큰수 구하기 알고리즘의 주요 아이디어입니다:
알고리즘 설명
- 주어진 배열의 길이만큼 결과 배열을 초기화합니다.
- 스택을 초기화합니다. 스택에는 배열의 인덱스가 저장됩니다.
- 배열을 왼쪽에서 오른쪽으로 순회합니다.
- 스택의 최상단에 있는 값(인덱스)을 확인합니다. 현재 원소가 그 인덱스의 원소보다 클 경우:
- 오큰수는 현재 원소입니다.
- 결과 배열에 해당 값을 저장합니다.
- 스택에서 해당 인덱스를 Pop합니다.
- 현재 인덱스를 스택에 Push합니다.
- 모든 원소에 대해 반복이 끝나면, 스택에 남아있는 인덱스는 오큰수가 없는 경우이므로 결과 배열에 -1을 설정합니다.
자바 구현
이제 위 알고리즘을 자바로 구현해보겠습니다.
import java.util.Stack;
public class NextGreaterElement {
public static int[] findNextGreaterElements(int[] nums) {
int n = nums.length;
int[] result = new int[n];
Stack stack = new Stack<>();
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
result[stack.pop()] = nums[i];
}
stack.push(i);
}
// 스택에 남은 인덱스는 오큰수가 없는 경우, -1로 설정
while (!stack.isEmpty()) {
result[stack.pop()] = -1;
}
return result;
}
public static void main(String[] args) {
int[] nums = {2, 1, 3, 2, 5};
int[] result = findNextGreaterElements(nums);
System.out.print("결과: [");
for (int i = 0; i < result.length; i++) {
System.out.print(result[i]);
if (i < result.length - 1) {
System.out.print(", ");
}
}
System.out.println("]");
}
}
시간 복잡도와 공간 복잡도
위에서 구현한 알고리즘은 시간 복잡도 O(N)입니다. 각 원소를 최대 한 번만 스택에 Push하고 Pop하기 때문입니다. 공간 복잡도는 스택을 최대 N만큼 사용할 수 있으므로 O(N)입니다.
결론
오큰수를 찾는 문제는 스택을 활용하여 효율적으로 해결할 수 있는 알고리즘 문제입니다. 이 문제는 코딩테스트에서 자주 출제되는 주제 중 하나이므로, 스택의 사용법 및 문제 해결 방법을 숙지해두는 것이 중요합니다. 다양한 예제를 통해 연습하여 문제 풀이 능력을 향상시키세요.