[백준/Java] 3649 로봇 프로젝트

🔗 문제 링크: https://www.acmicpc.net/problem/3649

🔍 해결 과정

결론적으로 이진탐색 방법을 활용하여 문제를 해결하였습니다. 처음에는 나노미터의 값을 인덱스로 받고 나노미터의 값이 존재하는지의 여부를 나타내는 배열을 활용하여 문제를 해결하려고 하였으나 문제에서 x의 최댓값은 20이므로 나노미터의 최댓값은 2억이 되어 Java에서 정수형 변수의 크기가 4 byte라는 점을 고려하면 762.94MB가 되어 메모리의 최댓값인 256MB를 훌쩍 넘깁니다. 

 

그래서 다른 방법을 생각한 결과가 이진탐색이었습니다. 이진탐색의 방법을 활용하면 목표로 하는 x의 값이 처음 일치했을 때 곧바로 |l2 - l1|의 값이 최대인 지점을 바로 구할 수가 있으며 또한 시간 복잡도 O(log n)에 걸쳐서 찾아낼 수가 있어 최댓값이 100만인 n에 대해서도 제한된 시간 안에 동작할 수가 있습니다. 설계 내용은 다음과 같습니다.

1. 정수형 배열 legos를 활용하여 레고 부품의 길이 정보를 모두 담는다.
2. legos 배열을 오름차순 정렬한다.
3. legos의 맨 왼쪽값과 맨 오른쪽 값을 시작으로 다음과 같은 과정을 진행한다.
   a. 만약 현재 가리키고 있는 legos의 왼쪽값과 현재 가리키고 있는 legos의 오른쪽값의 합이 x와 일치한다면 l1과 l2의 값을 추출하고 이진탐색을 종료한다.
   b. 만약 현재 가리키고 있는 legos의 왼쪽값과 현재 가리키고 있는 legos의 오른쪽값의 합이 x보다 작다면 legos의 왼쪽값을 가리키고 있는 인덱스를 오른쪽으로 한 칸 이동시킨다.
   c. 만약 현재 가리키고 있는 legos의 왼쪽값과 현재 가리키고 있는 legos의 오른쪽값의 합이 x보다 크다면 legos의 오른쪽값을 가리키고 있는 인덱스를 왼쪽으로 한 칸 이동시킨다.

 

 

---

✏️ 코드

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

public class Main {

    private static final String SPACE = " ";
    private static final String END_LINE = "\n";
    private static final String DANGER = "danger";
    private static final String YES = "yes";

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

        String xStr;
        while ((xStr = br.readLine()) != null) {
            int x = Integer.parseInt(xStr);
            int n = Integer.parseInt(br.readLine());
            int[] legos = new int[n];

            for (int i = 0; i < n; ++i) {
                legos[i] = Integer.parseInt(br.readLine());
            }

            Arrays.sort(legos);

            int nanoX = x * 10_000_000;
            int[] results = getResult(legos, n, nanoX);

            if (results == null) {
                sb.append(DANGER).append(END_LINE);
                continue;
            }

            sb.append(YES)
                    .append(SPACE)
                    .append(results[0])
                    .append(SPACE)
                    .append(results[1])
                    .append(END_LINE);
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private static int[] getResult(int[] legos, int len, int nanoX) {
        int leftIdx = 0;
        int rightIdx = len - 1;
        int[] result = null;

        while (leftIdx < rightIdx) {
            int lSum = legos[leftIdx] + legos[rightIdx];

            if (lSum == nanoX) {
                result = new int[]{legos[leftIdx], legos[rightIdx]};
                break;
            } else if (nanoX > lSum) {
                ++leftIdx;
            } else {
                --rightIdx;
            }
        }

        return result;
    }
}