[코딩테스트-SWEA] 3차원 농부 - Java 이진 탐색 문제 풀이

 

안녕하세요, 오늘은 삼성 SW Expert Academy의 "3차원 농부" 문제를 Java로 풀이한 내용을 공유드립니다. 이 문제는 대용량 데이터를 다루는 상황에서 이진 탐색을 활용해야 하는 전형적인 문제입니다.

---

📚 목차

1. 문제 개요
2. 문제 조건 요약
3. 핵심 아이디어
4. 알고리즘 설계
5. 자바 코드
6. 예제 입력/출력
7. 시간 복잡도
8. 마무리 정리

---

1. 문제 개요

농부 지민이는 특이하게도 소와 말을 3차원 공간에서 기릅니다. 모든 소는 (c1, 0, z) 위치에, 모든 말은 (c2, 0, z) 위치에 존재합니다.

소와 말 사이의 맨해튼 거리가 가까우면 이산화탄소가 많이 발생하므로, 지민이는 가장 가까운 소-말 쌍의 거리와 그러한 쌍의 개수를 알고 싶어합니다.

---

2. 문제 조건 요약

• 소와 말 각각 최대 50만 마리 (N, M ≤ 500,000)
• 위치는 3차원: (x, 0, z)
• 거리 계산: |x1 - x2| + |y1 - y2| + |z1 - z2|
• 모든 소는 x = c1, 말은 x = c2 → 결국 |c1 - c2|는 고정값

---

3. 핵심 아이디어

맨해튼 거리의 x축 차이는 고정되어 있으므로, z값 차이만 고려하면 된다!

• 거리 = |c1 - c2| + |z_cow - z_horse|
• |c1 - c2|는 고정 → |z_cow - z_horse|가 최소인 경우를 찾자!
• 말의 z좌표 하나마다 이진 탐색으로 소 배열에서 가장 가까운 값을 찾으면, 전체 최소값을 빠르게 구할 수 있다.

---

4. 알고리즘 설계

1. 소의 z좌표를 오름차순 정렬
2. 각 말의 z좌표에 대해 이진 탐색 수행
   • 가장 가까운 소의 z좌표를 찾아 |z_cow - z_horse| 계산
   • 최소 거리라면 갱신, 같으면 개수 증가
3. 마지막 출력: |c1 - c2| + minDistance, count

---

5. 자바 코드

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

class Solution {
    public static void main(String args[]) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int test_case = Integer.parseInt(in.readLine());
        for(int t = 0; t<test_case; t++ ){
            StringTokenizer st = new StringTokenizer(in.readLine());
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());
            int[] cow = new int[N];

            st = new StringTokenizer(in.readLine());
            int c1 = Integer.parseInt(st.nextToken());
            int c2 = Integer.parseInt(st.nextToken());

            st = new StringTokenizer(in.readLine());
            for(int i = 0; i<N; i++){
                cow[i] = Integer.parseInt(st.nextToken());
            }
            Arrays.sort(cow);

            int minValue = Integer.MAX_VALUE;
            int minCount = 0;

            st = new StringTokenizer(in.readLine());
            for(int i = 0; i<M; i++ ){
                int horse = Integer.parseInt(st.nextToken());
                int start = 0;
                int end = N-1;

                while(start <= end){
                    int mid = (start + end) / 2;
                    int dist = Math.abs(cow[mid] - horse);

                    if (dist < minValue) {
                        minValue = dist;
                        minCount = 1;
                    } else if (dist == minValue) {
                        minCount++;
                    }

                    if (cow[mid] < horse) {
                        start = mid + 1;
                    } else {
                        end = mid - 1;
                    }
                }
            }

            int dx = Math.abs(c1 - c2);
            bw.write("#" + (t+1) + " " + (dx + minValue) + " " + minCount + "\n");
        }

        bw.flush();
        bw.close();
    }
}

---

6. 예제 입력/출력

✅ 입력

1
3 3
0 2
1 2 3
5 6 7

✅ 출력

#1 4 1

• x축 거리: |0 - 2| = 2
• z좌표 최소 거리: |3 - 5| = 2
• 총 거리: 2 + 2 = 4
• 그런 쌍은 1개

---

7. 시간 복잡도

• 소 정렬: O(N log N)
• 말에 대해 이진 탐색: O(M log N)
• 전체: O(N log N + M log N) → 최대 2000만 연산으로 시간 내 통과 가능

---

8. 마무리 정리

이 문제는 단순한 완전 탐색으로는 시간 초과가 발생합니다. 핵심은 다음 두 가지입니다:

• 맨해튼 거리 계산에서 고정값을 분리
• 이진 탐색으로 거리 계산 최적화

대용량 데이터 처리 문제에서 자주 등장하는 패턴이므로, 잘 익혀두시면 좋습니다!

---

도움이 되셨다면 공감❤️과 댓글📝 부탁드립니다!
더 많은 코딩 테스트 풀이가 궁금하다면 [블로그 구독] 해주세요 😊

---