파이썬 알고리즘: 정렬된 배열에서 고정점(Fixed Point) 찾기

문제 설명

오름차순으로 정렬된 중복 없는 정수 배열 A가 주어졌을 때, A[i] == i를 만족하는 가장 작은 인덱스 i를 찾아 반환해야 합니다. 만약 그러한 인덱스가 존재하지 않으면 -1을 반환합니다.

예를 들어 배열이 [-10, -5, 0, 3, 7]이라면 결과는 3입니다. 이는 A[3] = 3, 즉 인덱스와 해당 위치의 값이 일치하기 때문입니다.

해결 접근 방법

이 문제는 선형 탐색(Linear Search)으로 간단하게 해결할 수 있습니다. 해결 단계는 다음과 같습니다.

• 인덱스 i를 0부터 배열 A의 길이 - 1까지 순서대로 순회합니다.
• 탐색 중 i == A[i]를 만족하면 해당 인덱스 i를 즉시 반환합니다.
• 모든 요소를 확인한 후에도 조건을 만족하는 인덱스가 없다면 -1을 반환합니다.

예제 코드 (Python)

아래 구현 예시를 통해 더 자세히 이해해 보겠습니다.

class Solution(object):
   def fixedPoint(self, A):
      for i in range(len(A)):
         if i == A[i]:
            return i
      return -1
ob1 = Solution()
print(ob1.fixedPoint([-10,-5,0,3,7]))

입력

[-10,-5,0,3,7]

출력

3

복잡도 분석

위 방법의 시간 복잡도는 O(n)이며, 추가적인 메모리를 사용하지 않으므로 공간 복잡도는 O(1)입니다.

배열이 이미 오름차순으로 정렬되어 있다는 특성을 활용하면 이진 탐색(Binary Search)을 적용할 수 있습니다. 이 경우 시간 복잡도를 O(log n)까지 줄여 더 큰 입력 데이터에서도 효율적으로 동작하게 할 수 있습니다.