5-P 질문 입니다 ㅠㅠ

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

5-P

해결된 질문

작성

345

강사님 안녕하세요,

5-P 문제를 먼저 풀고 예제에서는 모두 통과 한 것을 확인하고 제출해보니 94% 에서 틀렸다고 항상 나오네요...

저는 bitmask 활용하여 문제를 풀긴했습니다만
무엇이 틀렸는지 감이 오지를 않습니다.

같은 문제에 대한 다른 질문 글을 보니 90% 대에 틀렸다고 나오는 것이 있긴했는데

제 경우도 같은 경우일까요?

일부 주석 포함 제 코드는 다음과 같습니다.

http://boj.kr/8aa660e3d6fb407e81d7902b94b2d5a5

c++코딩-테스트

답변 1

큰돌

지식공유자

안녕하세요 KIM님 ㅎㅎ

해당 문제 비트연산으로 푸는거요.

예전에도 다른 수강생분이 질문하셔서 그 때 몇번 시도해보고 실패하고

이번에 KIM님이 말씀하셔서 또 한번 시도해봤는데.. 저도 이상하게 94%에서 틀렸다고 뜹니다..

제 코드는 다음과 같습니다.

http://boj.kr/7144c3d7011b4733a4979c80a4162b63

그냥 이 문제를 비트연산으로 푸는 것은 넘어가는게 좋을 거 같습니다.

도움이 되지 못해 죄송합니다.. ㅠ

또 질문 있으시면 언제든지 질문 부탁드립니다.

감사합니다.

강사 큰돌 올림.

Kyoung Jun Kim

질문자

강사님 안녕하세요,

비트연산 풀이 오답 관련 고민을 하다가 문제점을 확인하고 고치니
정답처리가 되어서 내용 공유드립니다.

정답 코드 : http://boj.kr/48af795d28a14ba8939bed26301704e6

최초 질문드렸을때 대비 코드에서 변경된 점이라고 하면,

최초 코드에서는, 회전 연산에 대해 bitshift 처리 하는 함수에서, bitshift 후에 8 비트 초과의 비트값에 대한 결과값을 그대로 출력을 했었는데요.

이렇게되면 반시계 방향으로 bitshift 가 계속 일어나는 경우 8비트 보다 큰 비트방향으로 1 이 누적이 되다보면 int 자료형의 overflow 가 발생할 수 있겠다는 생각이 들었습니다.

그래서, 아래 함수 보시면 return 단계에서 8 비트 초과하는 비트자릿수에 대해 bit_trim 처리를 해주니 overflow 가 없게 되어 정답처리가 되었습니다.

감사합니다.

int wheel_spin(int input, int dir)
{
  // wheel(input) 을 dir 방향으로 회전시켜서 회전된 결과를 int 로 return 하는 함수
  int output = input;
  int bit_trim = (1 << 8) - 1; // ...000011111111

  if (dir == CW)
  {
    output = output >> 1;
    if (input & (1 << 0))
    {
      output |= (1 << 7);
    }
  }
  else if (dir == CCW)
  {
    output = output << 1;

    if (input & (1 << 7))
    {
      output |= (1 << 0);
    }
  }

  // cout << "from : " << bitset<8>(input) << "\n";
  // cout << "to   : " << bitset<8>(output) << "\n";

  return (bit_trim & output); // shifting 결과에서 8비트 초과의 값은 0으로 처리 (오버플로우 방지)
}

큰돌

지식공유자

안녕하세요 KIM님 ㅎㅎ

저보다 똑똑하시네요 ㅎㅎ

사실 저 오늘 아침에 일어나서 아니 진짜 왜 틀리지? 하면서 다시 시도하고 있었는데

오버플로 생각지도 못했네요 ㅎㅎ 훌륭하십니다.

제코드에 + KIM님이 말씀하신 비트트림 추가하니까 맞았다고 뜹니다.

저또한 해당 코드 공유합니다.

http://boj.kr/fdfb8909c5b940fa99026f25c1714ab8

훌륭한 내용 공유 감사의 말씀을 드립니다.

인프런 커뮤니티 질문&답변

5-P 질문 입니다 ㅠㅠ