[ Codility ] - Lesson1 BinaryGap(C++)

문제조건

• 양의 정수 N
• N의 2진수 변환
• 2진수 1로 감싸진 가장 큰 0의 개수 반환

문제풀이

int solution(int N)
{
  int n = 0, cnt = 0, res = 0, f1 = 0;
  
  do {
    n = N % 2;					// N을 2로 나눈 나머지
    N /= 2;					// 다음 연산을 위한 나누기
    
    if (n == 1) { f1++ }			// 1일 경우에는 플래그를 세워준다
    if (f1 == 1 && n == 0) { cnt++; }		// 플래그가 세워졌을 때 n이 0이면 카운트
    else if (f1 == 2){
      if(res < cnt)
      {
        res = cnt;
        cnt = 0;
        f1 = 1;
      }
      else
      {
        cnt = 0;
        f1 = 1;
      }
    }						// 1을 한번 더 만나면 최댓값과 비교 후 저장하고 넘길지 그냥 넘길지 결정
  }while (N > 0);
  
  return res;
}

코드설명

  일단 기본적인 2진수 구하는 코드와는 다른 게 저희는 출력할 것이 아니라서 값을 저장할 변수가 필요 없고, 값을 할당하는 코드가 없어도 됩니다.

  작성 된 코드에 대한 설명으로는 플래그 값(f1)을 하나 둬서 1을 만나는 상황을 저장했습니다. 이를 이용해서 1일 동안에는 0의 개수를 세고, 2일 경우 즉 다음 1을 만났을 때는 지금까지 나온 최댓값과 비교하여 결과(res)에 저장하도록 했습니다. 결국 마지막에는 최대값으로 나온 res를 반환하여 프로그램이 성공적으로 돌아가게 했습니다.

결과사진