프로그래밍 및 알고리즘 테스트에서 빈번하게 등장하는 문제 중 하나는 ‘오큰수’ 문제입니다. 이 문제는 효율적인 알고리즘과 데이터 구조에 대한 이해를 요구하며, 다양한 실제 프로그래밍 상황에서도 매우 유용하게 적용될 수 있는 개념입니다.
문제 설명
문제: 주어진 정수 배열에서 각 숫자에 대해 그 숫자보다 큰 수 중에서 자신보다 오른쪽에 나오는 수를 찾고, 그 수를 출력하세요. 만약 존재하지 않는다면 -1을 출력합니다.
입력 형식
- 첫째 줄에 자연수 N (1 ≤ N ≤ 1,000,000)이 주어집니다.
- 둘째 줄에 N개의 정수로 이루어진 배열이 주어집니다. 값은 1 이상 1,000,000 이하입니다.
출력 형식
N개의 정수로 이루어진 배열을 출력하여 각 숫자에 대한 오큰수를 나타냅니다.
예시
입력
4
3 5 2 7
출력
5 7 -1 -1
문제를 푸는 방법
이 문제를 해결하기 위해서 스택(Stack) 자료구조를 활용할 것입니다. 스택은 LIFO(Last In, First Out) 구조로, 가장 나중에 들어온 데이터가 가장 먼저 나가는 특성을 가지고 있습니다. 이 구조를 사용하여 각 요소에 대해 오큰수를 효율적으로 찾을 수 있습니다.
알고리즘 설명
- 스택을 생성합니다. 이 스택은 인덱스를 저장할 것입니다.
- 주어진 배열을 순회합니다.
- 현재 숫자가 스택의 최상단에 있는 숫자보다 클 경우, 스택에서 인덱스를 꺼내고, 해당 인덱스에 현재 숫자를 오큰수로 저장합니다.
- 현재 인덱스를 스택에 추가합니다.
- 모든 숫자에 대해 이 과정을 반복한 후, 스택에 남아있는 인덱스는 오큰수가 존재하지 않는 것이므로 -1을 저장합니다.
코틀린 코드 구현
fun findNextGreater(nums: IntArray): IntArray {
val result = IntArray(nums.size) { -1 } // 결과 배열 초기화
val stack = mutableListOf() // 스택 생성
for (i in nums.indices) {
// 스택이 비어있지 않고 현재 수가 스택의 최상단의 수보다 클 경우
while (stack.isNotEmpty() && nums[stack.last()] < nums[i]) {
result[stack.removeAt(stack.size - 1)] = nums[i] // 오큰수 저장
}
stack.add(i) // 현재 인덱스 추가
}
return result
}
fun main() {
val inputArray = intArrayOf(3, 5, 2, 7)
val result = findNextGreater(inputArray)
print(result.joinToString(" ")) // 결과 출력
}
코드 설명
위의 코드는 오큰수를 찾는 알고리즘을 코틀린으로 구현한 것입니다. 주요 부분을 살펴보겠습니다.
1. 결과 배열 초기화
결과 배열은 오큰수를 저장하기 위한 배열입니다. 기본값으로 -1로 초기화합니다. 이는 오큰수가 존재하지 않을 경우를 처리하기 위함입니다.
2. 스택을 활용한 탐색
스택의 최상단 인덱스가 현재 인덱스 i가 가리키는 값보다 작은 경우, 그 인덱스를 꺼내고 해당 인덱스의 결과 배열에 현재 숫자를 할당합니다. 이 과정을 통해 오큰수를 찾아갑니다.
3. 최종 결과 출력
모든 숫자에 대해 탐색 후, 최종 결과 배열을 출력합니다. 결과는 주어진 배열의 각 수에 대한 오큰수가 저장된 상태로 출력됩니다.
성능 분석
이 방법의 시간복잡도는 O(N)입니다. 각 요소를 스택에 한 번씩 넣고 빼기 때문에 효율적입니다. 또한, 공간 복잡도는 O(N)으로 스택과 결과 배열을 사용하므로 사용된 메모리 양이 입력 크기에 비례합니다.
마무리
오늘은 코틀린을 이용하여 오큰수를 구하는 문제를 해결하는 방법을 알아보았습니다. 데이터 구조와 알고리즘의 중요성을 느끼셨기를 바라며, 앞으로도 알고리즘 문제 해결 능력을 키우기 위한 꾸준한 연습을 이어가시길 바랍니다.