[백준] 3009번 - 네 번째 점
문제
문제 설명 및 풀이
문제는 매우 간단하다. 만약 축에 평행하지 않았다면 기울기를 이용해서 구했어야 하지만 축에 평행하므로 같은 숫자가 또 나올 것이 분명하다. 결론적으로, 두 번 안나온 수가 곧 점의 좌표가 된다. 그러나 이를 그냥 if문의 나열로 풀면 너무 쉬우므로 같은 로직이지만 다른 풀이를 소개해보려 한다. 비트 연산의 쓰임을 알 수 있는 문제들 중 하나이다. 해당 문제에서는 XOR 비트연산이 쓰이므로, XOR의 성질을 적어보겠다.
XOR 연산은 기본적으로, 비트가 서로 다르면 1, 같으면 0이 된다. 이와 관련하여 갖는 성질로 아래 두 가지가 있다.
- 값이 0인 변수에 X로 XOR 연산을 하면 해당 변수는 X가 된다. 값이 0인 변수는 모든 비트가 0이므로 1인 비트에 대한 부분만 1로 바뀌기 때문이다.
ex) 00000 ^ 11110 = 11110 - 값이 X인 변수에 Y로 XOR 연산을 두 번 하면 원래의 값 X가 된다. 처음 연산에서 값이 변경된 부분만 다시 변경되기 때문이다.
ex) (11110 ^ 01010) ^ 01010 = 10100 ^ 01010 = 11110
이러한 성질을 이용하면 사각형의 나머지 꼭지점을 빠르게 찾아낼 수 있다. 이를 코드로 표현하면 아래와 같다.
