C++로 풀어보는 홀수·짝수 점프(Odd Even Jumps) 문제

문제 개요

배열 A가 주어져 있다고 가정해 봅시다. 어떤 시작 인덱스에서 출발하여 일련의 점프를 수행할 수 있으며, 이때 1번째, 3번째, 5번째... 점프를 '홀수 번째 점프', 2번째, 4번째, 6번째... 점프를 '짝수 번째 점프'라고 부릅니다.

인덱스 i에서 앞쪽 인덱스 j(i < j)로 점프하는 규칙은 다음과 같습니다.

• 홀수 번째 점프: A[i] <= A[j]를 만족하면서 A[j]가 가능한 한 가장 작은 값이 되는 인덱스 j로 점프합니다. 후보 인덱스가 여러 개라면 그중 가장 작은 인덱스로만 이동할 수 있습니다.

• 짝수 번째 점프: A[i] >= A[j]를 만족하면서 A[j]가 가능한 한 가장 큰 값이 되는 인덱스 j로 점프합니다. 마찬가지로 후보가 여러 개일 경우 가장 작은 인덱스를 선택합니다.

• 어떤 인덱스 i에서는 유효한 점프 자체가 존재하지 않을 수도 있습니다.

특정 시작 인덱스에서 출발했을 때 몇 번의 점프를 거쳐 배열의 끝에 도달할 수 있다면, 그 인덱스를 '좋은(good) 시작 인덱스'라고 부릅니다. 우리가 구해야 할 것은 바로 이 좋은 시작 인덱스의 개수입니다.

예를 들어 입력이 [10, 13, 12, 14, 15]라면 출력은 2가 됩니다. 인덱스 3(값 14)과 인덱스 4(값 15)에서 출발하면 배열의 끝까지 도달할 수 있기 때문입니다.

풀이 접근 방식

이 문제는 정렬된 맵(map)과 동적 계획법(DP)을 결합하면 효율적으로 해결할 수 있습니다. 먼저 각 인덱스에서 홀수 점프와 짝수 점프로 이동하게 될 '다음 인덱스'를 미리 계산해 둔 뒤, 배열의 끝에서부터 역순으로 도달 가능 여부를 전파하는 방식입니다.

구체적인 알고리즘 단계는 다음과 같습니다.

• 결괏값 ret을 1로 초기화하고, n을 배열 A의 크기로 설정합니다.

• 크기가 n인 두 배열 nextGreaterEqual과 nextSmallerEqual을 선언하고 -1로 초기화합니다. 각각 홀수 점프 시 이동할 다음 인덱스와 짝수 점프 시 이동할 다음 인덱스를 저장합니다.

• 정렬된 맵 st를 하나 선언합니다.

• i를 n-1부터 0까지 감소시키며 다음을 반복합니다.

  • it := 맵 st에서 키가 A[i]보다 크거나 같은 첫 번째 키-값 쌍(lower_bound 결과)

  • nextGreaterEqual[i] := it가 마지막 요소가 아니면 it의 값, 그렇지 않으면 -1

  • 만약 it가 st의 끝이 아니고 it의 키가 A[i]와 같다면 it를 1 증가시킵니다.

  • nextSmallerEqual[i] := it가 첫 번째 요소가 아니면 바로 앞 요소의 값, 그렇지 않으면 -1

  • st[A[i]] := i (현재 인덱스를 맵에 기록)

• 크기가 n × 2인 2차원 불리언 배열 v를 선언하고 false로 초기화합니다. v[i][1]은 i에서 홀수 번째 점프를 했을 때, v[i][0]은 짝수 번째 점프를 했을 때 끝에 도달할 수 있는지를 나타냅니다.

• v[n-1][0]과 v[n-1][1]을 true로 설정합니다. 마지막 인덱스는 이미 목표 지점이므로 항상 성공입니다.

• i를 n-2부터 0까지 감소시키며 다음을 반복합니다.

  • nextGreaterEqual[i]가 -1이 아니라면 v[i][1] := v[nextGreaterEqual[i]][0]으로 갱신합니다. (홀수 점프 후에는 짝수 점프 차례)

  • nextSmallerEqual[i]가 -1이 아니라면 v[i][0] := v[nextSmallerEqual[i]][1]로 갱신합니다. (짝수 점프 후에는 홀수 점프 차례)

  • v[i][1]이 참이라면 ret을 1 증가시킵니다. 첫 점프는 항상 홀수 번째이기 때문입니다.

• 최종적으로 ret을 반환합니다.

이 방법의 시간 복잡도는 O(n log n)(맵 연산이 지배), 공간 복잡도는 O(n)입니다. 완전 탐색으로는 비효율적인 문제를 선형 로그 시간 안에 해결할 수 있습니다.

C++ 구현 예제

아래 코드를 통해 실제 구현을 확인해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int oddEvenJumps(vector<int>& A){
      int ret = 1;
      int n = A.size();
      vector<int> nextGreaterEqual(n, -1);
      vector<int> nextSmallerEqual(n, -1);
      map<int, int> st;
      for (int i = n - 1; i >= 0; i--) {
         map<int, int>::iterator it = st.lower_bound(A[i]);
         nextGreaterEqual[i] = (it != st.end()) ? it->second : -1;
         if (it != st.end() && it->first == A[i])
         it++;
         nextSmallerEqual[i] = it != st.begin() ? prev(it)->second
         : -1;
         st[A[i]] = i;
      }
      vector<vector<bool> > v(n, vector<bool>(2, false));
      v[n - 1][0] = v[n - 1][1] = true;
      for (int i = n - 2; i >= 0; i--) {
         if (nextGreaterEqual[i] != -1) {
            v[i][1] = v[nextGreaterEqual[i]][0];
         }
         if (nextSmallerEqual[i] != -1) {
            v[i][0] = v[nextSmallerEqual[i]][1];
         }
         if (v[i][1])
         ret++;
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<int> v = {10,13,12,14,15};
   cout << (ob.oddEvenJumps(v));
}

입력

{10,13,12,14,15}

출력

2

마무리

홀수·짝수 점프 문제는 단순히 시뮬레이션하면 지수적으로 늘어나는 경로를 모두 따져야 하지만, lower_bound 기반 맵 조회로 '유일하게 유효한 다음 점프'를 O(log n)에 찾고 DP로 도달 가능성을 역방향 전파함으로써 효율적인 해결이 가능합니다. 정렬된 자료구조와 동적 계획법을 함께 활용하는 대표적인 패턴이므로, 코딩 테스트 대비에 꼭 익혀두면 유용합니다.