문제 설명
주어진 정수 배열 arr
이 있을 때, 배열의 각 원소는 0 이상의 정수입니다. 각 원소에 대해, 해당 원소의 오른쪽에 있는 원소들 중에서 자신보다 큰 첫 번째 원소의 인덱스를 구하여 새로운 배열을 만들고 이를 반환하는 문제입니다. 만약 그런 원소가 없다면 –1을 저장합니다.
예를 들어, 배열이 [2, 1, 5, 3, 6, 4]
라면, 결과는 [2, 1, 1, 1, -1, -1]
입니다.
문제 접근 방법
이 문제는 스택을 이용하여 효율적으로 접근할 수 있습니다. 전체 배열을 한 번만 탐색하면서, 스택을 사용하여 각 원소의 오른쪽에서 발생하는 문제를 해결할 수 있습니다. 이렇게 하면 시간 복잡도를 줄일 수 있습니다.
알고리즘 설명
- 결과를 저장할 배열
result
를 초기화합니다. - 스택을 초기화하여 인덱스를 저장합니다.
- 배열을 오른쪽에서 왼쪽으로 순회합니다.
- 현재 요소가 스택의 마지막 요소보다 크면, 스택에서 요소를 pop하여 결과 배열의 해당 인덱스에 값을 저장합니다.
- 스택이 비어있다면, 결과 배열에는
-1
을 저장합니다. - 현재 인덱스를 스택에 추가합니다.
- 최종 결과 배열을 반환합니다.
코드 구현
func nextGreaterElement(arr: [Int]) -> [Int] {
var result = Array(repeating: -1, count: arr.count)
var stack: [Int] = []
for i in (0..
코드 설명
코드는 다음과 같이 구성되어 있습니다:
result
: 결과를 저장할 배열을 -1로 초기화합니다.stack
: 인덱스를 저장할 스택을 초기화합니다.reversed
: 배열을 거꾸로 탐색합니다. 오른쪽에서 왼쪽으로 진행하는 이유는 각 원소의 오른쪽에 있는 요소를 비교하기 위함입니다.- 스택에서 pop 작업을 통해 자신보다 큰 원소를 찾습니다.
- 찾은 인덱스를 결과 배열에 업데이트하고, 현재 인덱스를 스택에 추가합니다.
시간 복잡도
이 알고리즘은 각 원소를 스택에 단 한 번만 추가하고 제거하므로, 시간 복잡도는 O(n)
입니다. 이는 매우 효율적입니다.
결론
이 강좌에서는 스택을 사용하여 주어진 문제를 효율적으로 해결하는 방법을 배웠습니다. 스택과 큐는 여러 코딩 인터뷰 문제에서 자주 등장하는 자료구조입니다. 따라서, 이 두 자료구조에 대한 이해와 활용이 중요합니다.
이 문제를 풀어보면서 자신만의 문제 해결 방식을 개발하고, 다양한 문제를 시도해 보세요. 스택과 큐에 대한 더 많은 문제는 나중에 다루도록 하겠습니다.