[BOJ] 백준 [17124] 두개의배열 JAVA

https://www.acmicpc.net/problem/17124

17124번: 두 개의 배열

📝문제

📝풀이

이분탐색 or 이진탐색 문제이다.

해당 위치를 기준으로 앞 뒤를 파악해야 하므로 lower higher 메서드를 제공해주는
TreeSet을 이용한다.

B 배열이 기준이므로 B배열을 TreeSet으로 만든다음
A 배열 원소만큼 반복문을 돌린다.

찾은 결과 원소를 result 라고 하면  
1. bSet 이 원소 e 를 가지고 있을 경우 => result = e
2. 가지고 있지 않을 경우
  2-1. bSet 에 e 를 추가해서 lower higher 를 호출
  2-2. lower = null => 추가한 원소가 맨 앞 자리이므로 result = higher
        higher = null => 추가한 원소가 맨 뒷 자리이므로 result = lower
        그 외 => e-lower 과 e-higher 를 비교해서 가장 차이가 적은 것이 result

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.stream.Collectors;

import static java.util.Arrays.stream;


public class Main {

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

        int tc = Integer.parseInt(br.readLine());
        while (tc-->0){ br.readLine();

            long sum = 0L;

            ArrayList<Integer> listA = stream(br.readLine().split(" "))
                    .mapToInt(Integer::parseInt)
                    .boxed()
                    .collect(Collectors.toCollection(ArrayList::new));

            TreeSet<Integer> setB = stream(br.readLine().split(" "))
                    .mapToInt(Integer::parseInt)
                    .boxed()
                    .collect(Collectors.toCollection(TreeSet::new)); // 기준 Set

            for (Integer e : listA) {

                int result=e; // 기준 Set 에 이미 있는 요소이면 바로 출력

                if(!setB.contains(e)){ // 없는 요소이면 위치 찾기

                    // 추가한 요소의 앞 뒤 확인
                    setB.add(e);
                    Integer lower = setB.lower(e);
                    Integer higher = setB.higher(e);

                    if(lower == null) // 맨 앞자리일 경우
                        result = higher;
                    else if(higher==null)  // 맨 뒷자리일 경우
                        result = lower;
                    else result = Math.abs(e - lower) <= Math.abs(e - higher) ?
                                lower : higher; // lower-e-higher >> 이 형태로 있으므로 앞 뒤 차이 계산해서 결정

                    setB.remove(e); // 다시 제거
                }
                sum+=(long)result;
            }
            System.out.println(sum);
        }
    }
}

/**

 *
 */