[백준/JAVA] BOJ 9024 - 두 수의 합

투 포인터를 마스터 해 보겠습니다!
사실 유형이 거의 비슷해서 날먹인 것 같기두............

👀 문제

9024번: 두 수의 합 ✨ 골드 5

당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 지나갈 수 없거나, 비어있어서 지나갈 수 있게 되어있다. 당신은 각 칸에서 인접한 6개의 칸(동,서,남,북,상,하)으로 1분의 시간을 들여 이동할 수 있다. 즉, 대각선으로 이동하는 것은 불가능하다. 그리고 상범 빌딩의 바깥면도 모두 금으로 막혀있어 출구를 통해서만 탈출할 수 있다.

당신은 상범 빌딩을 탈출할 수 있을까? 만약 그렇다면 얼마나 걸릴까?

예제 입력

3 4 5
S....
.###.
.##..
###.#

#####
#####
##.##
##...

#####
#####
#.###
####E

1 3 3
S##
#E#
###

0 0 0

예제 출력

Escaped in 11 minute(s).
Trapped!

🔑 키포인트

너비 우선 탐색

✍️ 코드

📍 투 포인터의 정석 같은 느낌의 문제. 오름차순으로 정렬해 주고 left = 0 right = n - 1 에 포인터를 놓고 탐색해 준다. 두 수의 합이 k보다 크다면 right를 한 칸 줄여주고, k보다 작으면 left를 한 칸 늘려준다.

💡 가장 k와 가까운 합을 near_value 에 저장해 놓고, 합이 해당 값과 같다면 개수 (answer)를 늘려준다. 만약 합이 near_value 보다 작다면 개수 1로 초기화 후 near_value 를 해당 합으로 갱신해 준다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BOJ9024_두수의합 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        int t = Integer.parseInt(st.nextToken());
        for (int tc = 0; tc < t; tc++) {
            st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int k = Integer.parseInt(st.nextToken());

            int[] arr = new int[n];
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < n; i++) {
                arr[i] = Integer.parseInt(st.nextToken());
            }
            Arrays.sort(arr); // 오름차순 정렬
            int answer = 0;
            int near_value = Integer.MAX_VALUE;
            int left = 0;
            int right = n - 1;

            while (left < right) {
                int hab = arr[left] + arr[right];
                if (arr[left] + arr[right] > k) {
                    right--;
                } else {
                    left++;
                }
                if (Math.abs(hab - k) < near_value) {
                    answer = 1;
                    near_value = Math.abs(hab - k);
                } else if (Math.abs(hab - k) == near_value) {
                    answer++;
                }
            }
            sb.append(answer + "\n");
        }
        System.out.print(sb.toString());
    }
}