AI 안쓰고 풀면 짱


문제: 작은 개구리 한 마리가 강 건너편으로 가고 싶어 합니다. 개구리는 처음에 강의 한쪽 강둑(위치 0)에 있었고, 반대편 강둑(위치 X+1)으로 가고 싶어 합니다. 나무에서 나뭇잎이 강물 위로 떨어졌습니다.

떨어지는 나뭇잎을 나타내는 N개의 정수로 구성된 배열 A가 주어집니다. A[K]는 시간 K에서 나뭇잎 하나가 떨어지는 위치를 초 단위로 나타냅니다.

목표는 개구리가 강 건너편으로 점프할 수 있는 가장 빠른 시간을 찾는 것입니다. 개구리는 강 건너편 1부터 X까지 모든 위치에 나뭇잎이 나타날 때만 건너갈 수 있습니다(즉, 1부터 X까지 모든 위치가 나뭇잎으로 뒤덮이는 가장 빠른 순간을 찾고자 합니다). 강물의 흐름 속도가 무시할 수 있을 정도로 작다고 가정할 수 있습니다. 즉, 나뭇잎은 강에 떨어진 후에도 위치가 변하지 않습니다.

예를 들어, 정수 X = 5와 배열 A가 주어졌을 때 다음과 같습니다.

A[0] = 1 A[1] = 3 A[2] = 1 A[3] = 4 A[4] = 2 A[5] = 3 A[6] = 5 A[7] = 4

두 번째 6에서 잎이 위치 5로 떨어집니다. 이는 강 건너편의 모든 위치에 잎이 나타나는 가장 빠른 시간입니다.

함수를 작성하세요:

def solution(X, A)

N개의 정수와 정수 X로 구성된 비어 있지 않은 배열 A가 주어졌을 때, 개구리가 강 반대편으로 점프할 수 있는 가장 빠른 시간을 반환합니다.

만약 개구리가 강 반대편으로 점프할 수 없다면, 함수는 -1을 반환해야 합니다.

예를 들어, X = 5이고 배열 A가 다음과 같다고 가정합니다.

A[0] = 1 A[1] = 3 A[2] = 1 A[3] = 4 A[4] = 2 A[5] = 3 A[6] = 5 A[7] = 4

위에서 설명한 대로 함수는 6을 반환해야 합니다.

다음 가정에 대한 효율적인 알고리즘을 작성하세요 .

  • N과 X는 [ 1 .. 100,000 ] 범위 내의 정수입니다 .
  • 배열 A의 각 요소는 [ 1 .. X ] 범위 내의 정수입니다 .