스위프트 코딩테스트 강좌, 스택과 큐

문제 설명

주어진 정수 배열 arr이 있을 때, 배열의 각 원소는 0 이상의 정수입니다. 각 원소에 대해, 해당 원소의 오른쪽에 있는 원소들 중에서 자신보다 큰 첫 번째 원소의 인덱스를 구하여 새로운 배열을 만들고 이를 반환하는 문제입니다. 만약 그런 원소가 없다면 –1을 저장합니다.

예를 들어, 배열이 [2, 1, 5, 3, 6, 4]라면, 결과는 [2, 1, 1, 1, -1, -1]입니다.

문제 접근 방법

이 문제는 스택을 이용하여 효율적으로 접근할 수 있습니다. 전체 배열을 한 번만 탐색하면서, 스택을 사용하여 각 원소의 오른쪽에서 발생하는 문제를 해결할 수 있습니다. 이렇게 하면 시간 복잡도를 줄일 수 있습니다.

알고리즘 설명

  1. 결과를 저장할 배열 result를 초기화합니다.
  2. 스택을 초기화하여 인덱스를 저장합니다.
  3. 배열을 오른쪽에서 왼쪽으로 순회합니다.
    • 현재 요소가 스택의 마지막 요소보다 크면, 스택에서 요소를 pop하여 결과 배열의 해당 인덱스에 값을 저장합니다.
    • 스택이 비어있다면, 결과 배열에는 -1을 저장합니다.
    • 현재 인덱스를 스택에 추가합니다.
  4. 최종 결과 배열을 반환합니다.

코드 구현

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)입니다. 이는 매우 효율적입니다.

결론

이 강좌에서는 스택을 사용하여 주어진 문제를 효율적으로 해결하는 방법을 배웠습니다. 스택과 큐는 여러 코딩 인터뷰 문제에서 자주 등장하는 자료구조입니다. 따라서, 이 두 자료구조에 대한 이해와 활용이 중요합니다.

이 문제를 풀어보면서 자신만의 문제 해결 방식을 개발하고, 다양한 문제를 시도해 보세요. 스택과 큐에 대한 더 많은 문제는 나중에 다루도록 하겠습니다.