문제 설명
solution 함수에 X, A 값이 주어집니다.
개구리가 강을 건너기 위한 최소한의 시간을 출력하는 문제입니다.
개구리의 초기 위치는 index 0이며, X 위치까지 도달하기 위해서는 반드시 모든 위치에 낙엽이 떨어져야 합니다.
바로 예시를 보겠습니다.
A[0] = 1
A[1] = 3
A[2] = 1
A[3] = 4
A[4] = 2
A[5] = 3
A[6] = 5
A[7] = 4
위와 같이 매 시간별 낙엽이 떨어지는 위치가 주어지고 개구리는 X=5까지 도달해야 합니다.
이 때, 1-2-3-4-5 위치에 모두 낙엽이 존재해야하며, 한번 떨어진 낙엽은 사라지지 않습니다.
접근 방법
한번 떨어진 낙엽은 사라지지 않는다 => Visited 배열로 방문처리를 해줍니다.
매 번 낙엽이 떨어질 때, O(N)만큼의 탐색을 반복하면 시간초과가 발생할 것 입니다. N은 최대 10만번이니까요.
그래서 낙엽이 새로 떨어질 때(낙엽이 없는 공간) X를 1만큼 감소시켜 X가 0이 되는 순간 정답을 출력합니다.
X가 0이 됐다는 것은 1부터 X까지 낙엽이 모두 떨어졌다는 뜻이기 때문입니다.
만약 A 배열을 모두 탐색했다면, X까지 모든 낙엽이 떨어지지 않았다는 뜻이기 때문에 -1을 출력합니다.
소스 코드
Python
def solution(X,A):
visited = [0]*100001
sec = 0
for i in range(len(A)):
sec+=1
if not visited[A[i]]:
visited[A[i]]=1
X-=1
if not X:
return sec-1
return -1
print(solution(5, [1, 3, 1, 4, 2, 3, 5, 4]))Java8
#