페이스북 생활 코딩에 재미있는 문제가 나와서 문제 풀이를 해 봅니다.

https://www.facebook.com/groups/codingeverybody/permalink/1706502986056897/




대략적인 해결 방법은 다음 2가지 정도가 있겠습니다.


1. 덧셈 연산을 이용하기

2. xor 연산을 이용하기




숫자 하나가 빠져 있는 간단한 클래스를 만듭니다.


template <class T>
struct NextNo {
  T omit_;
  T no_{0};
  NextNo(T omit) : omit_(omit) {}
  T next() {
    if (++no_ == omit_)
      no_++;
    return no_;
  }
};



덧셈을 이용하는 방법입니다. 40억 범위의 문제가 있기 때문에 overflow를 고려하여 uint64_t를 사용해야 합니다.실제 1~40억까지의 합은 CNT*(CNT+1)/2 로 구할 수 있습니다.


// --------------------------------------------------------------------------
// sum_test(uint64_t)
// --------------------------------------------------------------------------
{
  NextNo<uint64_t> nextNo((uint64_t)omitNo);
  uint64_t sum = 0;
  for (uint64_t i = 1; i < CNT; i++)
    sum += nextNo.next();
  cout << (uint64_t)CNT * (CNT + 1) / 2 - sum << endl;
}




xor을 이용하는 방법입니다. xor을 이용하면 40억 범위의 문제가 발생하지 않기 때문에 uint32_t로도 처리할 수 있습니다.


// --------------------------------------------------------------------------
// xor_test(uint32_t)
// --------------------------------------------------------------------------
{
  NextNo<uint32_t> nextNo(omitNo);
  uint32_t sum1 = 0, sum2 = 0;
  for (uint32_t i = 1; i < CNT; i++) {
    sum1 ^= i;
    sum2 ^= nextNo.next();
  }
  sum1 ^= CNT;
  cout << (sum1 ^ sum2) << endl;
}




이왕 하는 김에 xor 연산을 uint64_t에서도 해 보겠습니다.


// --------------------------------------------------------------------------
// xor_test(uint64_t)
// --------------------------------------------------------------------------
{
  NextNo<uint64_t> nextNo((uint64_t)omitNo);
  uint64_t sum1 = 0, sum2 = 0;
  for (uint64_t i = 1; i < CNT; i++) {
    sum1 ^= i;
    sum2 ^= nextNo.next();
  }
  sum1 ^= CNT;
  cout << (sum1 ^ sum2) << endl;
}




[실행결과]


Intel® Core™ i5-5200U CPU @ 2.20GHz × 4  / g++ version 6.3.0 / -O2 option


sum_test(uint64_t)

#./omit_test 1

1

real 0m5.280s


#./omit_test 1000000

1000000

real 0m5.276s


#./omit_test 4000000000

4000000000

real 0m5.277s


xor_test(uint32_t)

#./omit_test 1

1

real 0m5.748s


#./omit_test 1000000

1000000

real 0m5.728s


#./omit_test 4000000000

4000000000

real 0m5.749s


xor_test(uint64_t)

#./omit_test 1

1

real 0m5.749s


#./omit_test 1000000

1000000

real 0m5.725s


#./omit_test 4000000000

4000000000

real 0m5.731s




[결론]


sum_test(uint64_t) : 5.277 sec

xor_test(uint32_t) : 5.741 sec

xor_test(uint64_t) : 5,735 sec


add와 xor의 OP Code상의 실행 클럭 수는 동일하므로 실행 속도에도 차이는 없다.

64bit machine에서 uint32_t, uint64_t의 실행 속도는 상관이 없다.




[download]


omit_test.zip


You would..