FrogRiverOne

작은 개구리가 강을 건너가려고 합니다.
개구리는 처음에 강의 한쪽 둔덕(위치 0)에 있으며, 반대편 둔덕(위치 X+1)으로 가고자 합니다.
나뭇잎들이 강 표면에 떨어집니다.

배열 A는 떨어지는 나뭇잎들을 나타내는 N개의 정수로 이루어져 있습니다.
A[K] 는 K초(시간 K)에 나뭇잎이 떨어진 위치를 의미합니다.

목표:
개구리가 강 반대편으로 건널 수 있는 가장 이른 시각을 구하세요.
개구리는 1부터 X까지 모든 위치에 나뭇잎이 놓였을 때만(즉, 1..X의 모든 위치가 덮였을 때만)
건널 수 있습니다.
강의 유속은 무시할 수 있을 정도로 매우 작다고 가정하며, 한 번 떨어진 나뭇잎의 위치는 변하지 않습니다.

예시:
X = 5
A = [1, 3, 1, 4, 2, 3, 5, 4]

6초에 위치 5에 나뭇잎이 떨어집니다.
이 시점에서 1..5의 모든 위치가 나뭇잎으로 덮이므로, 개구리가 건널 수 있는 가장 이른 시각은 6입니다.

함수 규격:
class Solution {
    public int solution(int X, int[] A);
}
- 비어 있지 않은 정수 배열 A와 정수 X가 주어졌을 때,
  개구리가 강을 건널 수 있는 가장 이른 시각을 반환합니다.
- 만약 끝까지 모든 위치(1..X)가 덮이지 않아 개구리가 건널 수 없다면, -1을 반환합니다.

효율적 알고리즘 조건:
- N, X는 [1..100,000] 범위의 정수입니다.
- 배열 A의 각 원소는 [1..X] 범위의 정수입니다.

public class FrogRiverOne
{
    public int solution(int X, int[] A)
    {
        bool[] coveredLeaf = new bool[X + 1]; 
        int nextLeaf = 1;                      
 
        for (int i = 0; i < A.Length; i++)
        {
            int pos = A[i];
 
            // 이미 덮인 나뭇잎 무시
            if (coveredLeaf[pos])
                continue;    
            
            // 나뭇잎 덮기
            coveredLeaf[pos] = true;           
 
            // 연속해서 덮인 만큼 nextLeaf를 앞으로 밀어줌
            while (nextLeaf <= X && coveredLeaf[nextLeaf])
                nextLeaf++;
 
            // 모두 덮이면 nextLeaf == X+1
            if (nextLeaf == X + 1)
                return i;                      
        }
 
        return -1; // 끝까지 못 덮이면 -1
    }
}