백준 - 투 포인터 2470번 두 용액 / 문제풀이, 오답노트

= 내가 접근한 방법 =

1. 주어진 제한 시간은 1초, n의 범위를 생각하면 2중 for문으로는 분명히 시간 초과 !

따라서 투 포인터 알고리즘 사용

 

2. 0번째 index 값과, n - 1번째 index값을 비교 합한 후, 절댓값을 씌우고 최솟값을 계속 갱신한다.

최솟값을 갱신하면서 index의 값도 갱신.

 

= 내가 틀린 이유 =

1. 맨 처음 값과 맨 마지막 값의 합을 비교하면서

 1-1. 0보다 클때, end값을 증가

 1-2. 0보다 작을 때, start값을 증가

 1-3. 0일 때, break;

라는 조건을 생각해야 되는데

절댓값을 씌운 상태에서 이 3가지 조건문을 사용했다.

 

절댓값이 없는 그냥 순수한 합을 통해서 이 3개의 조건문대로 움직였어야했는데 실수했다.

 

절댓값을 씌우고 if문이 진행이 되면 무조건 end--만 실행되기 때문이다.

 

= 정답 코드 =

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
    public static void main(String[] args) throws IOException {
        // 1. input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine()); // 용액의 수 n
        int[] arr = new int[n];
 
        // 주어진 제한 시간은 1초, n의 범위는 -1,000,000,000 이상 1,000,000,000 이하
        // 2중 for 문을 사용해서 해결하는 문제가 아니라, 투 포인터를 알고리즘 활용
 
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        } // 용액을 담는 배열
        // 최종적으로 0과 가장 가까운 값을 찾는 것이다.
 
        // 2. 맨 왼쪽 값과 맨 오른쪽 값을 비교한다.
        // 두 수의 합을 절댓값 씌우고, 최솟값을 계속 갱신하면서 두 수의 값( -98, 99처럼 )도 계속 갱신.
 
        Arrays.sort(arr);
 
        int start = 0;
        int end = n - 1;
 
        int min = Integer.MAX_VALUE;
        int number = 0; // number 값으로 최솟값을 찾는다
        int a = 0; // 두 수 중 하나
        int b = 0; // 두 수 중 하나 ( 두 수의 합이 0이랑 가까울 때, 그 때 index 값이 a, b다. )
        int check = 0; // check 값으로 index 번호를 조정할 수 있게한다
        while (start < end) {
            check = arr[start] + arr[end];
            number = Math.abs(arr[start] + arr[end]);
 
            if (min > number) {
 
                min = number;
                a = arr[start];
                b = arr[end];
            }
            if (check > 0) {
                end--;
            } else if (check < 0) {
                start++;
            } else if (check == 0) {
                break;
            }
        }
 
        System.out.println(a + " " + b);
    }
}