[HackerRank] Bit Array

https://www.hackerrank.com/challenges/bitset-1/problem

Bit Array | HackerRank

문제 풀이)

 

나타나는 숫자의 개수를 세는 문제이다. 예를 들어 1, 2, 3, 4, 0, 1, 2, 3, 4 와 같이 나왔다면 1, 2, 3, 4, 0 으로 총 5가지의

 

수가 나타났음을 출력해주면 된다.

 

set이나 map을 unordered로 선언하고 해도 시간초과가 난다. 그 이유는 총 1억개의 수가 중복되지 않는다면

 

1억개의 원소가 추가되고, 이 연산은 시간을 감당할 수 없기 때문이다.

 

친구랑 같이 고민을 하다, 친구가 괜찮은 방법을 생각해 냈다.

 

괜찮은 방법이란 마지막 수를 기준으로 중복이 있는 지 찾아보고, 없다면 총 개수가 숫자의 개수가 되는 것이고 만약

 

중복이 있다면 중복이 나타나는 gap을 찾아 중복이 되지 않는 곳을 찾을 때까지 count를 증가시켜주는 방식이다.

 

위에서 예를 든 1, 2, 3, 4, 0, 1, 2, 3, 4 에서 마지막 수는 '4'이다.

 

4에서 아래로 가면서 중복된 수를 보면 3번 째 인덱스에 있고 이 사이의 갭은 5임을 알 수 있다.

 

3번 째 인덱스의 '4'가 가장 먼저 나타난 '4'이며, 가장 먼저 나타난 '4' 이전은 모두 처음 나타난 수를 보장받을 수

 

있다고 보았다.

 

'4'에서 이제 인덱스를 증가시켜보면서 루프가 나타날 때까지 count ( 숫자의 개수 ) 를 증가시킨다.

 

즉 count는 4에서 시작해서 '0'을 만나 5가 되고, '0' 다음의 '1'을 만났을 때 종료되면서 답을 도출해낼 수 있다.

 

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;
#define MOD 0x80000000

int main() {
	unsigned long long n, s, p, q;
	cin >> n >> s >> p >> q;
	int gap = 0;
	vector<int> v;

	v.resize(n);
	v[0] = s;
	for (int i = 1; i < n; ++i)
	{
		int val = (s * p) % MOD;
		val = (val + q) % MOD;
		s = val;
		v[i] = val;
	}

	int nCount = n;
	// 마지막 원소 기준
	int tmp = v[n - 1];
	for (int i = n - 2; i >= 0; --i)
	{
		// 루프를 찾았을 경우
		if (tmp == v[i])
		{
			// 갭 설정
			gap = n - i - 1;

			int j, t;
			for (j = i - gap; j >= 0; j -= gap)
				if (v[j] != tmp) break;
			j += gap;

			// 찾은 곳부터 올라가면서 루프가 아닌 것을 찾기
			for (t = j + 1; t < n; ++t)
				if (gap <= t && v[t] == v[t - gap]) break;

			nCount = t;
			break;
		}
	}
	cout << nCount << '\n';

	return 0;
}