문제 탐색하기

입력 자료 정리

1. 입력값 n은 전체 용액의 개수이다
2. 이후 들어오는 n개의 값은 -10^9 ~ 10^9범위의 용액의 특성 값이다.

해결방법 추론

1. 문제에서 왜 굳이 알칼리성과 산성 용액으로 나누어주었을까?라는 의문을 품고 문제를 접근하였다
2. 이 문제를 가장 쉽게 해결하는 방법은 완전탐색하는 것이다. 하지만 시간초과가 발생한다
3. 그렇다면 알칼리성과 산성 용액을 하나씩 잡아서 비교한다면?
   더 나아가서 정렬한 뒤에 양 끝점을 잡고 비교한다면? 정답을 찾을 수 있지 않을까 생각했다
4. 그냥 두 지점의 값을 합했을 때 음수면 왼쪽을 조절하고, 양수면 오른쪽을 조절하면서
   차이가 가장 0에 가까운 값을 찾으면 문제를 해결할 수 있을 것이다

시간복잡도 계산

1. 시간복잡도는 n의 범위 내에서 투포인터로 연산을 진행중이기 때문에
   O(n)이 될 것이다
2. 따라서 시간제한안에 문제를 해결할 수 있다

코드 설계하기

입력값 상태 관리하기

1. n은 변수로 관리하고, 각 값은 int형 배열로 관리한다
2. 투포인터 로직을 위해 배열을 오름차순 정렬해주자
3. 또한 정답값을 담기 위한 ansL과 ansR도 선언해주었고,
   차이가 0에 가까운 값을 찾기 위해 Integer.MAX_VALUE 값을 갖는 diff 변수도 선언하였다

구현 코드 설계

1. left와 right는 인덱스 범위의 양 끝지점으로한다
2. left <= right인 동안 단순히 합한값과 차이를 구한다음,
   diff보다 차이가 작다면 정답을 갱신해준다
3. 이어서 앞서 추론한대로 mid가 0보다 크면 right를 조절하고 반대는 left를 조절한다

출력값 설계

1. 완성한 ansL과 ansR에 해당하는 배열의 값을 출력하면 정답이 될텐데...

시도회차 수정

1회차 시도 실패

1. 25%에서 틀려버렸다
2. 원인이 무엇일까 분석해보니 left<=right가 문제였다
3. 선택하는 두 용액은 같은 용액이면 안된다. 서로 다른 두개의 용액을 혼합한다고 되어있기 때문이다
4. 따라서 left < right로 탐색범위를 변경하였다.

2회차 시도 성공

1. 변경한 로직으로 시도했을 때, 성공했다

정답코드

(1회차 시도 실패)

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


public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);

        int ansL = 0;
        int ansR = 0;
        int diff = Integer.MAX_VALUE;

        int left = 0;
        int right = n - 1;
        while(left <= right){
            int mid = arr[left] + arr[right];
            int tmp = Math.abs(mid);
            if(diff > tmp){
                ansL = left;
                ansR = right;
                diff = tmp;
            }

            if(mid > 0){
                right--;
            }else {
                left++;
            }
        }

        bw.write(arr[ansL] + " " + arr[ansR]);

        br.close();
        bw.close();
    }

}

(2회차 시도 성공)

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


public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);

        int ansL = 0;
        int ansR = 0;
        int diff = Integer.MAX_VALUE;

        int left = 0;
        int right = n - 1;
        while(left < right){
            int mid = arr[left] + arr[right];
            int tmp = Math.abs(mid);
            if(diff > tmp){
                ansL = left;
                ansR = right;
                diff = tmp;
            }

            if(mid > 0){
                right--;
            }else {
                left++;
            }
        }

        bw.write(arr[ansL] + " " + arr[ansR]);

        br.close();
        bw.close();
    }

}

문제링크

2470번 - 두 용액