Codility lesson1 - BinaryGap

안녕하세요 오늘은 Codility가 코딩테스트에 자주 사용된다는 이야기을 듣고 구경하러 갔는데요.

영어로 된 사이트라서 어떤걸 해야할지 잘 모르겠더라구요... ㅠ

들어가자마자 보이는 lesson 카테고리에서 간단하게 몇문제 풀어 볼 수 있어서 도전해봤습니다.

 

문제는 영문으로 나와서 구글 번역기 돌려서 풀었습니다... ㅠ

 

요약

정수를 Input 받아서 2진수로 변환 후 1과 1사이에 나오는 0의 최대 길이를 Output으로 내면 됩니다.

예를 들어 9 -> 1001 : 2    //  529 -> 1000010001 : 4  입니다.

1과 1사이에 존재하지 않는 0은 카운팅 하지 않습니다. 32 -> 100000 : 0

 

아이디어

1. 정수를 2진수로 만들어 String으로 저장한다.

2. String의 앞에서부터 0을 계속 카운팅하면서 1이 두번 들어오면 카운팅을 유효로 봅니다.

 

코드

int solution(int N) {
	// write your code in C++14 (g++ 6.2.0)
	string strnum = "";
	int first = -1, second = -1;
	int sol = 0;
	while (N)
	{
		if (N % 2 == 1)
		{
			strnum.append("1");
		}
		else
		{
			strnum.append("0");
		}
		N = N / 2;
	}
	for (int i = strnum.size()-1; i>=0 ; i--)
	{
		if (strnum[i] == '1')
		{
			if (first == -1)
				first = i;
			else if (second == -1)
				second = i;
			else
			{
				first = second;
				second = i;
			}

			if (first != -1 && second != -1)
			{
				sol = max(first - second - 1,sol);
			}
		}
	}
	return sol;
}

결과는

 

부담스럽게 느껴지지는 않아서 1트만에 통과했는데요.

제가 작성한 코드가 마음에 안들어서 다른 사람들의 코드를 살펴봤는데 마음에 드는 알고리즘이 있어서 참고해서 다시 풀었습니다.

 

int solution(int N)
{
	int maxGap = 0;
	int Gap = 0;
	bool cntflag = false;

	while (N) {
		if ((N & 1) == 1)
		{
			if (!cntflag)
			{
				cntflag = true;
			}
			else if (Gap > maxGap)
			{
				maxGap = Gap;
			}
			Gap = 0;
		}
		else {
			Gap++;
		}
		N = N >> 1;
	}
	return maxGap;
}

비트연산을 이용한 코드입니다.

문제를 풀기 몇일전 C++에 관련된 글들을 보다가 나누기 연산이 가장 느리고 2로 나누는경우 ">> 1"을 사용하게 되면 연산속도가 개선이 많이 된다는 글을 봤었는데 막상 문제를 풀때는 적용이 안됬는지... 더 노력해야될것 같네요.

추가적으로 cntflag를 사용하지 않고 풀 수 없을까 생각했는데 N==1 && maxGap == 0인 케이스가 cntflag 인데요.

&& 연산에서 왼쪽항이 false면 오른쪽항을 보지 않기때문에 비교 횟수는 비슷할 것으로 보이나 코드가 짧더라도 직관적으로 보이기에는 cntflag가 좋아보여서 이방법을 선택했습니다.

간단하고 짧은 문제이지만 극도로 간소화 시킬 수 있는 방법을 고민해볼 수 있었던 문제였던것 같네요.

혹시 다른방법이 있으면 링크로 공유 부탁드려욥

남은 lesson 문제도 차차 풀어나가보겠습니다.

 

고민해볼 수 있게되는 댓글은 저를 성장시킵니다.