Lesson 4 Counting Elements FrogRiverOne 나만의풀이

문제

A small frog wants to get to the other side of a river. The frog is initially located on one bank of the river (position 0) and wants to get to the opposite bank (position X+1). Leaves fall from a tree onto the surface of the river.

You are given an array A consisting of N integers representing the falling leaves. A[K] represents the position where one leaf falls at time K, measured in seconds.

The goal is to find the earliest time when the frog can jump to the other side of the river. The frog can cross only when leaves appear at every position across the river from 1 to X (that is, we want to find the earliest moment when all the positions from 1 to X are covered by leaves). You may assume that the speed of the current in the river is negligibly small, i.e. the leaves do not change their positions once they fall in the river.

For example, you are given integer X = 5 and array A such that:

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

In second 6, a leaf falls into position 5. This is the earliest time when leaves appear in every position across the river.

Write a function:

• def solution(X, A)

that, given a non-empty array A consisting of N integers and integer X, returns the earliest time when the frog can jump to the other side of the river.

If the frog is never able to jump to the other side of the river, the function should return −1.

For example, given X = 5 and array A such that:

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

the function should return 6, as explained above.

Write an efficient algorithm for the following assumptions:

• N and X are integers within the range [1..100,000];
• each element of array A is an integer within the range [1..X].

대충 해석하자면 개구리가 강을 건너려고 하는데 leaves라는 다리가 전부 내 앞에 있어야 건널수 있다는 뜻

X는 건너야 할 다리 길이고 1부터 X까지의 다리가 전부 모이면 건너는데 그 때의 A 배열의 index를 출력하라는 것이다.

 

 

첫번째 시도 겸 두번째 시도

따로 넣을까 하다가 단순한 실수라서 그냥 텍스트로 적어넣는다.

첫번째 시도는 건너지 못한다면 -1을 리턴해야하는데 까먹고 안해서 틀렸다

두번째 시도는 -1 넣어서 바로 성공

def solution(X, A):
    leaves = {}
    for index, val in enumerate(A):
        if val not in leaves:
            leaves[val] = 0
            if len(leaves.values())==X:
                return index
    return -1

 

 

복잡도 O(N)

난이도가 Painless라서 그런지 10분만에 후딱 푼 문제다.