직사각형의 나머지 한 점의 좌표 - XOR 연산자 (Javascript)

---

부트캠프 지원할 때 봤던 코딩테스트 문제 중 하나이다.

구글링하면 같은 문제가 검색이 잘 되는 걸 보니, 이미 예전부터 여러 곳에서 볼 수 있는 고전적인 문제임을 알 수 있다.

문제는 풀기 쉽지만 다양한 방법의 풀이를 생각해볼 필요가 있다.

복기하는 문제들은 자세한 설명이나 제한조건을 적기 힘들기 때문에 문제와 풀이 위주로만 기록한다.

---

문제

• 주어진 배열에는 세 개의 좌표가 주어집니다. 이 좌표들은 직사각형의 세 꼭지점을 나타냅니다. 나머지 한 점의 좌표를 찾아 반환하는 함수를 구현하세요.

입출력 예시

입력	출력
[[1, 2], [4, 2], [1, 4]]	[4,4]
[[2, 5], [8, 5], [2, 9]]	[8, 9]
[[-1, 0], [3, 0], [-1, 2]]	[3, 2]

---

풀이 1

단순한 좌표의 덧셈과 뺄셈

function findCoor(rectangle) {
    // x좌표 
    const x_coor = rectangle[0][0] + rectangle[1][0] - rectangle[2][0]

    // y좌표
       const y_coor = rectangle[0][1] + rectangle[2][1] - rectangle[1][1] 
    
    // 구하려는 좌표
      answer = [x_coor, y_coor]

    return answer;
}

// 예시 입력
const rectangle = [[1, 2], [4, 2], [1, 4]];

// 결과 출력
const result = findCoor(rectangle);
console.log(result);  // [4, 4]

 

주의할 점

해당 문제는 입력된 좌표의 순서가 랜덤이었음.

만약 입력 순서가 랜덤일 경우 이렇게 가로와 세로 길이를 활용해서 구하는 방법도 있음.

function findCoor(rectangle) {
    // 가로 길이
    const width = Math.max(rectangle[2][0], rectangle[0][0], rectangle[1][0]) - Math.min(rectangle[2][0], rectangle[0][0], rectangle[1][0]);

    // 세로 길이
    const height = Math.max(rectangle[0][1], rectangle[1][1], rectangle[2][1]) - Math.min(rectangle[0][1], rectangle[1][1], rectangle[2][1]);

    // x좌표
    const x_coor = Math.min(rectangle[2][0], rectangle[0][0], rectangle[1][0]) + width;

    // y좌표
    const y_coor = Math.min(rectangle[0][1], rectangle[1][1], rectangle[2][1]) + height;

    // 구하려는 좌표
    const answer = [x_coor, y_coor];

    return answer;
}

// 예시 입력 (랜덤한 순서)
const Input1 = [[4, 2], [1, 4], [1, 2]];
const Input2 = [[-1, 0], [3, 0], [-1, 2]];

// 결과 출력
const result1 = findCoor(Input1);
console.log(result1);  // [ 4, 4 ]

const result2 = findCoor(Input2);
console.log(result2);  // [ 3, 2 ]

 

풀이 2

XOR 연산자 활용

풀다보면 원가 더 간단히 할 수 있을 것 같아서 찾아보니 비트 연산자를 활용한 풀이가 있었다.

function find(rectangle) {
    // 각 좌표의 XOR 연산을 통해 나머지 좌표 찾기
    const coor = [
        rectangle[0][0] ^ rectangle[1][0] ^ rectangle[2][0],
        rectangle[0][1] ^ rectangle[1][1] ^ rectangle[2][1]
    ];

    return coor;
}

// 예시 입력
const input = [[1, 2], [4, 2], [1, 4]];

// 결과 출력
const result = find(input);
console.log(result);

 

 

좀 더 일반화된 풀이

const input = [[1, 2], [4, 2], [1, 4]];

var answer = [0, 0];
for (let i = 0; i < input.length; i++) {
    answer[0] ^= input[i][0];
    answer[1] ^= input[i][1];
}

console.log(answer); // [4, 4]

input의 배열 안 원소 개수가 일정하지 않다면 이렇게 풀어야 됨.

 

XOR 연산자

· XOR(exclusive or) 연산은 두 비트가 다를 때 1을 반환하고, 같을 때는 0을 반환하는 논리 연산
· 동일한 비트에 대해 두 번 XOR하면 원래 값으로 돌아가는 특징이 있음.

X좌표	Y좌표
1 ^ 4 ^ 1	2 ^ 2 ^ 4
이진수로 변환하면: 001 ^ 100 ^ 001	이진수로 변환하면: 010 ^ 010 ^ 100
XOR 적용 결과: 100 (이진수로)	XOR 적용 결과: 100 (이진수로)
10진수로 변환하면: 4	10진수로 변환하면: 4