[3009] 네 번째 점

난이도: ★★★☆☆ • solved on: 2025-07-20

---

문제 요약

• 문제 유형: 구현, 수학
• 요구사항: 세 점이 주어졌을 때, 직사각형을 만들기 위한 네 번째 점의 좌표를 구해야 한다.

---

사용 개념

1. 자료구조

   • 2차원 배열 (int[][]) 또는 HashMap<Integer, Integer>

2. 알고리즘/기법

   • 좌표의 개수 세기
   • XOR 또는 HashSet을 통한 짝수 개수 제거

3. 핵심 키워드

   • 좌표 쌍
   • 직사각형의 성질: 각 좌표축별로 같은 값이 2개씩 나온다

---

풀이 아이디어 및 코드

방법 1: 좌표 개수 세기 (if 기반)

1. 문제 분해
   • x와 y 각각에 대해 세 점 중 유일하게 한 번만 등장한 값이 네 번째 점의 좌표이다.
2. 핵심 로직 흐름

   - axis[0] → x좌표 배열
   - axis[1] → y좌표 배열
   - 각 좌표 배열에서, 같은 값이 2번 나오면 그 값은 생략
   - 나머지 한 번만 나온 값을 추출

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line;
        int[][] axis = new int[2][3];
        int[] answer = new int[2];

        for (int i = 0; i < 3; i++) {
            line = br.readLine().split(" ");
            axis[0][i] = Integer.parseInt(line[0]); // x
            axis[1][i] = Integer.parseInt(line[1]); // y
        }

        for (int i = 0; i < 2; i++) {
            int[] tmp = {0, 0};
            for (int j = 0; j < 3; j++) {
                if (j == 0) {
                    tmp[0] = axis[i][j];
                } else {
                    if (tmp[1] == 0 && axis[i][j] != tmp[0]) {
                        tmp[1] = axis[i][j];
                        if (j == 2) answer[i] = tmp[1];
                    } else if (axis[i][j] == tmp[0] && tmp[1] != 0) {
                        answer[i] = tmp[1];
                    } else if (axis[i][j] == tmp[1]) {
                        answer[i] = tmp[0];
                    }
                }
            }
        }

        System.out.println(answer[0] + " " + answer[1]);
    }
}

---

방법 2: HashMap으로 개수 세기 (가독성 개선)

1. 각 좌표의 빈도를 Map에 저장한 뒤, 빈도 1인 값을 출력

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Map<Integer, Integer> xMap = new HashMap<>();
        Map<Integer, Integer> yMap = new HashMap<>();

        for (int i = 0; i < 3; i++) {
            String[] input = br.readLine().split(" ");
            int x = Integer.parseInt(input[0]);
            int y = Integer.parseInt(input[1]);

            xMap.put(x, xMap.getOrDefault(x, 0) + 1);
            yMap.put(y, yMap.getOrDefault(y, 0) + 1);
        }

        int x = 0, y = 0;
        for (int key : xMap.keySet()) {
            if (xMap.get(key) == 1) {
                x = key;
                break;
            }
        }
        for (int key : yMap.keySet()) {
            if (yMap.get(key) == 1) {
                y = key;
                break;
            }
        }

        System.out.println(x + " " + y);
    }
}

---

방법 3: XOR 사용 (좌표가 정확히 두 번씩만 나오는 성질 이용)

1. XOR은 같은 값이 두 번 나오면 0이 되므로, 세 점을 XOR하면 남는 하나의 값이 바로 답

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int x = 0, y = 0;
        for (int i = 0; i < 3; i++) {
            x ^= sc.nextInt();
            y ^= sc.nextInt();
        }

        System.out.println(x + " " + y);
    }
}

---

시간·공간 복잡도

방법 1

• 시간 복잡도: O(1)
• 공간 복잡도: O(1)

방법 2

• 시간 복잡도: O(1)
• 공간 복잡도: O(1) (Map 크기는 최대 3)

방법 3 (XOR)

• 시간 복잡도: O(1)
• 공간 복잡도: O(1)

---

어려웠던 점

• 방법1의 경우, 남은 한 점을 찾기 위해 조건문을 여러 개 작성했는데, 조합이 많다 보니 흐름을 제어하는 것이 까다로웠다.
• 방법1의 경우, 조건의 우선순위와 분기처리를 정확히 하지 않으면 로직이 틀어지므로 디버깅에 시간이 오래 걸렸다.

---

배운 점 및 팁

• 직사각형 좌표에서 같은 좌표가 두 번씩만 등장한다는 성질을 활용하면 XOR 또는 HashMap으로 간단히 해결할 수 있다.
• 중복을 제거하거나 개수를 세는 문제는 Set, Map, XOR을 고려해보자.
• 간단한 패턴이 있는 문제는 조건 분기보다 수학적 규칙을 먼저 생각하면 깔끔하게 풀 수 있다.
• getOrDefault()는 Map을 쓸 때 빈도 수 카운팅에 매우 유용하다.
• XOR은 짝수 번 등장한 숫자를 제거하고 홀수 번 등장한 숫자만 남기는 데 특화되었기에. 이 문제처럼 “두 번 등장한 것을 제거하고 하나만 남기고 싶은” 상황에 적합하다.

  방법2와 방법3에서 사용된 메소드 및 연산자

  방법 2: HashMap을 사용한 개수 세기

  메소드 / 구문	설명
  map.getOrDefault(key, defaultValue)	key가 존재하면 해당 값을 반환, 없으면 기본값 반환
  map.put(key, value)	key에 해당하는 값을 삽입하거나 덮어씀
  map.keySet()	현재 저장된 모든 key 값을 반환

  ---

  방법 3: XOR 연산을 사용한 좌표 추출

  연산자 / 구문	설명
  ^ (XOR)	비트 단위 배타적 논리합: 같은 값이면 0, 다르면 1
  x ^= value	x에 value를 XOR한 결과를 다시 x에 저장

• 비트 단위 배타적 논리합 ($XOR$, ^)의 활용

  1. XOR 의 정의

  XOR (Exclusive OR) 연산은 두 값이 서로 다를 때만 1, 같으면 0을 반환하는 비트 연산

  진리표 (Truth table)

  A	B	A ^ B
  0	0	0
  0	1	1
  1	0	1
  1	1	0

  "서로 다르면 1, 같으면 0"

  예제 1: 정수의 XOR 연산

  : 정수는 내부적으로 2진수(비트)로 표현된다.

  int a = 5;  // 0101 (2진수)
  int b = 3;  // 0011
  int result = a ^ b; 
  // 0101 ^ 0011 = 0110 → 10진수로 6 

  ---

  예제 2: x ^= value 가 의미하는 것

  : x에 x와 value의 XOR 연산 결과를 다시 저장한다.

  ---

  실제 활용된 원리

  입력:

  1 4  
  3 4  
  1 10

  x좌표: 1, 3, 1
  y좌표: 4, 4, 10

  x좌표에서 1이 두 번, 3이 한 번 등장하므로
  1 ^ 3 ^ 1 = (1 ^ 1) ^ 3 = 0 ^ 3 = 3
  따라서 정답 x는 3

  y좌표에서 4 ^ 4 ^ 10 = 0 ^ 10 = 10

  같은 값이 두 번 XOR 되면 사라진다(0이 된다)는 성질을 이용한 것.

  ---

  XOR 연산의 특징 요약

  특징	설명
  A ^ A = 0	같은 값을 두 번 XOR 하면 0이 된다
  A ^ 0 = A	0과 XOR 하면 자기 자신이 된다
  결합법칙, 교환법칙 가능	순서와 묶음이 바뀌어도 결과는 같음
  활용	짝수 번 등장한 값 제거, 유일한 값 찾기

---

참고 및 링크

• 문제 링크: https://www.acmicpc.net/problem/3009
• 참고 블로그/깃허브: 없음

---

추가 연습 문제

• 비슷한 유형 (GPT 추천):

  • [15894] 수학은 체육과목입니다 (도형과 수학적 규칙)
  • [2476] 주사위 게임 (조건 분기 + 수학)

• 확장 문제 (GPT 추천):

  • 사각형의 네 꼭짓점이 주어졌을 때, 직사각형인지 판단하는 문제
  • n개의 점 중 4개를 골라 직사각형을 만들 수 있는지 여부 판별 문제