문제
작은 개구리는 강 반대편으로 가고 싶어한다. 개구리는 처음에 강의 한 뱅크(위치 0)에 위치하며 반대편 뱅크(위치 X+1)로 이동하려고 합니다. 나뭇잎이 나무에서 강의 수면으로 떨어진다.
낙엽을 나타내는 N개의 정수로 구성된 배열 A가 주어집니다. A[K]는 K 시간에 한 잎이 떨어지는 위치를 나타내며, 초 단위로 측정됩니다.
목표는 개구리가 강 반대편으로 점프할 수 있는 가장 빠른 시기를 찾는 것이다. 개구리는 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로 떨어집니다. 이것은 강을 가로지르는 모든 위치에 나뭇잎이 나타나는 가장 빠른 시기이다.
함수 쓰기:
분해능(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]를 클릭합니다.
코드
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(X, A):
dictionary={}
for iter in range(len(A)):
key=A[iter]
value=iter
#딕셔너리로 변경함
if key in dictionary:
dictionary[key]=min(dictionary[key],value)
else:
dictionary[key]=value
max_number=0
#최대값 찾기
for index in range(1,X+1):
#가다가 길이 없으면 -1 리턴
if index not in dictionary:
return -1
else:
max_number=max(max_number,dictionary[index])
return max_number
예외처리
