[ Codility ] - Lesson4 FrogRiverOne(C++)

문제조건

• 개구리가 가려고 하는 위치까지의 길이 X
• 값이 정의된 벡터 A

문제 설명

  이 문제는 위치 0에 있는 개구리가 목표지점까지 가기 위해서 X만큼의 거리를 가는데 걸리는 시간을 구하는 문제입니다. 인트형 벡터 A를 던져주는데 이는 A[K]형태로 봤을 때, K를 1초로 보면 될 것 같습니다. 그래서 초마다 나뭇잎이 하나씩 A[K]의 위치에 떨어지는데 그 위치가 중복되는 것은 상관이 없습니다. 그렇게 목적지까지 가기 위해 모든 자리에 나뭇잎이 채워지면 마지막 나뭇잎이 떨어진 시간(초)을 반환하며 문제를 마치면 됩니다.

이런 느낌이라고 보면 될 것 같습니다.

문제풀이

int solution(int X, vector &A) {
    int cnt = 0;			// 목표지점에 도달하기 위해 깔린 나뭇잎의 개수
    int flag[X+1] = {0,};		// 나뭇잎이 특정 위치에 떨어져 있는지 확인

    for (int i = 0; i < A.size(); ++i)
    {
        if(flag[A[i]] == 0)		// 나뭇잎이 필요한 위치에 있는지 확인
        {
            flag[A[i]]++;
            cnt++;
        }
        if(cnt == X) { return i; } 	// 목적지까지 나뭇잎이 떨어지는 데 걸린 시간 반환
    }
    return -1;
}

코드설명

  일단 반복문을 통해 나뭇잎이 떨어지는 과정을 돌립니다. 그다음 flag변수를 통해 이미 그 자리에 나뭇잎이 떨어졌었는지 아니면, 비었는지 확인합니다. 나뭇잎이 이미 있다면 넘어가고, 나뭇잎이 없다면 flag[]에 1을 더해서 있다고 표시해 준 뒤 cnt 변수도 1씩 늘려줍니다. 그렇게 cnt가 목적지까지 가는 나뭇잎의 수를 충족한다면 그 충족하게 된 시간 K(여기선 i)를 반환해주면 됩니다. 그리고 마지막까지 나뭇잎이 1자리 이상 비는 상황이 되면, -1을 반환하며 프로그램을 마쳐줍니다.

결과사진