DRAWRECT 문제가 bitwise operator로 풀리는 이유가 무엇일까요

  • dongie
    dongie

    DRAWRECT 문제를 풀고난 후 python 최저라인 코드를 보니 다음과 같이 신박하게 접근하셨더라구요. ^는 bitwise operator로 알고 있는데... 왜 아래 코드를 돌리면 마지막 점이 나오는지에 대한 논리적 이해가 잘 되지 않아서 글을 올려봅니다.

    for _ in xrange(input()):
    x = y = 0
    for _ in xrange(3) :
        p = map(int, raw_input().split())
        x ^= p[0]
        y ^= p[1]
    print x, y
    • 참고로 제 접근 방법은 다음과 같았습니다
      • 사각형은 각각 같은 라인에 2점씩 위치하게 됩니다.
      • 때문에 x축 좌표와, y축 좌표에 있어서 각각 2개씩 존재하게 됩니다.
      • 총 입력받은 3개의 좌표죽에 같은 x축 ,y축 값이 없는 좌표를 출력

    8년 전
2개의 댓글이 있습니다.
  • dongie
    dongie

    곰곰히 생각해 보니 이해가 가네요 -
    0^a = a
    a^b = c
    c^a = b, c^b = a 의 느낌이네요.


    8년 전 link
  • thebarbershop
    thebarbershop

    정확히는 임의의 a에 대하여 a^a=0이고 0^a=a^0=a이기 때문입니다.
    그렇다면 a^a^b=b이고 a^b^b=a가 되겠네요. 교환법칙 결합법칙도 성립하기 때문에 입력이 어떤 순서로 들어오든 그냥 차례대로 XOR 하기만 하면 됩니다.


    8년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.