백준 3009번: 네 번째 점, XOR와 등장 횟수로 찾기

한 번만 나온 좌표를 찾습니다

백준 3009번은 축에 평행한 직사각형의 세 꼭짓점을 보고 나머지 한 점을 찾는 문제입니다.

네 꼭짓점 전체를 보면 같은 x좌표가 두 번씩, 같은 y좌표도 두 번씩 나옵니다. 그래서 세 점만 있을 때 한 번 나온 x좌표와 한 번 나온 y좌표를 고르면 네 번째 점이 됩니다. XOR 연산을 쓰는 방법과 좌표별 등장 횟수를 세는 방법으로 각각 풀었습니다.

XOR로 같은 값을 지웁니다

정수의 XOR 연산은 비트가 다르면 1, 같으면 0을 만듭니다. 같은 정수를 두 번 XOR하면 0이 되고 어떤 정수를 0과 XOR하면 그 정수가 남습니다. 세 점의 x좌표끼리, y좌표끼리 각각 XOR하면 짝이 없는 좌표만 남습니다.

Java

import java.io.*;
import java.util.*;

class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int x = 0, y = 0;
        // 비트 마스킹 방법 ^ (XOR) 연산을 사용 저장된 값과 다르면 참, 같으면 거짓
        for (int i = 0; i < 3; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            x = x ^ Integer.parseInt(st.nextToken());
            y = y ^ Integer.parseInt(st.nextToken());
        }
        bw.write(x + " " + y);
        bw.flush();
    }
}

좌표가 나온 횟수를 셉니다

두 번째 코드는 x좌표와 y좌표의 등장 횟수를 따로 저장해 두었다가 입력을 모두 받은 뒤 횟수가 1인 좌표를 찾아 출력합니다. 빈도만 세는 방식이라 정렬 결과를 만드는 카운팅 정렬과는 다릅니다. 아래 두 코드는 독립된 제출 코드입니다.

Java

import java.io.*;
import java.util.*;

class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 계수 정렬 알고리즘 (counting sort algorithm) 사용
        int[][] arrX = new int[1001][1];
        int[][] arrY = new int[1001][1];

        for (int i = 0; i < 3; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            arrX[x][0]++;
            arrY[y][0]++;
        }
        int tX = 0;
        int tY = 0;

        // 값을 받은 뒤 중복되지 않은 값을 출력한다.
        for (int i = 1; i < 1001; i++) {
            if (arrX[i][0] == 1) {
                tX = i;
            }
            if (arrY[i][0] == 1) {
                tY = i;
            }
        }
        bw.write(tX + " " + tY);
        bw.flush();
    }
}