Codility lesson4_1 - FrogRiverOne

요약

개구리가 강 건너편으로 이동을 하려하는데 이동해야하는 거리는 X이고 낙엽이 떨어지는 곳을 나타낸 벡터 A이다.

벡터 A에는 1초마다 낙엽이 떨어지는 곳을 나타낸다. X까지 낙엽이 모두 있어야 개구리가 건널 수 있다. X와 벡터 A와 정수 X를 input으로 받아서 몇초만에 목표지점에 도착하는지 정수로 output해야한다. 도달할 수 없는 경우 -1

예를 들어 

X = 5

A[0] = 1      개구리 -> oxxxx 강건너편

A[1] = 3                    oxoxx

A[2] = 1                    oxoxx

A[3] = 4                    oxoox

A[4] = 2                     oooox

A[5] = 3                    oooox

A[6] = 5                    ooooo

A[7] = 4                    ooooo

라고하면 6초만에 강 건너편으로 도달 할 수 있게 된다.

 

아이디어

A벡터에서 다른 공간으로 낙엽이 떨어지는 공간을 중복없이 넘겨주어서 X와 크기가 같아지는 시점이 개구리가 강건너편으로 이동할 수 있는 시간으로 판단

 

코드

#include<unodered_set>
int solution(int X, vector<int> &A) {
	// write your code in C++14 (g++ 6.2.0)
	unordered_set<int> leaf;
	unordered_set<int>::iterator it;
	int cnt = 0;
	for (auto element : A)
	{
		
		it = leaf.find(element);
		if (it == leaf.end())
			leaf.insert(element);

		if (leaf.size() == X)
			return cnt;

		cnt++;
	}
	return -1;
}

 

결과는

 

unodered_set을 이전문제에서도 사용했었는데 관련 함수사용해볼겸 한번 더 사용했습니다. unodered_set을 이용하여 공간의 크기가 목표 지점과 같으면 cnt를 리턴하고 끝까지 도달 못할 시 -1반환하도록 작성했습니다.

어렵지 않다.