[알고리즘] 투 포인터 / 이진 탐색(binary search)

백준 2467 투 포인터 풀이

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{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		long[] arr = new long[n];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0; i<n; i++) {
			arr[i] = Long.parseLong(st.nextToken());
		}
		
        // left는 0번 right는 n-1번 인덱스 시작
		int left =0;
		int right =n-1;
        
        // 0에 제일 근접했던 start, end 인덱스 기록용 변수
		int ml =0, mr = 0;
		long min = Long.MAX_VALUE;
		while(left<right) {
			long sum = arr[left]+arr[right];
			if(min > Math.abs(sum)) {
				min = Math.abs(sum);
				ml = left; mr = right;
			}
			if(sum>=0) {
				right--;	
			}else {
				left++;
			}
		}
		System.out.println(arr[ml] +" "+arr[mr]);
	}
}

얻어갈 점:

• 투 포인터로 풀이할 수 있는 이유? 두 개의 용액이 -부터 +까지 정렬된 상태에서 두 개를 골라 0에 최대한 근접한 값을 찾는다(구간 합과 유사) => 양 쪽 끝에서 두 개를 고른 다음 0보다 크면 start를 하나 땡기고 0보다 작으면 end를 하나 땡기고
• left > right while 조건문 작성할 때 ==일 때를 고려했는데 2개를 골라야하니 같으면 안 되어서 빼줌
• if(sum>=0) => 해당 부분 sum==0과 sum>0로 나눌까 합칠까 고민했는데 합침 => 반복 도중 1번째로 0이 된 결과값이 있다면 위의 최소값과 좌우 인덱스 저장시 반영되고 , 2번째 나오는 0부터는 어차피 기록이 안 됨=> min>Math.abs(sum)을 만족 시키지 못하기 때문 => 굳이 나눌 필요없이 right--로 통일해도 문제 없음

---

백준 2467 이진 탐색 풀이

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

public class Main {

	static int n;
	static long[] arr;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		
		arr = new long[n];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0; i<n; i++) {
			arr[i] = Long.parseLong(st.nextToken());
		}
		
		long min = Long.MAX_VALUE;
		int ml =0, mr = 0;
        
        
        // i가 0일때부터 순차적으로 증가하며 기준이 됨
		for(int i=0; i<n-1; i++) {
			int left =i+1;
			int right =n-1;
			while(left<=right) {
            
            //기준이 되는 i를 제외한 left 와 right의 중간 지점 찾기
				int mid = (left+right)/2;
				long sum = Math.abs(arr[i]+arr[mid]);
				
                //최소값 발견시 해당 좌우 인덱스와 최소값 기록
				if(min > sum) {
					min = sum;
					ml = i; mr = mid;
				}
				if(arr[mid]>= -arr[i]) {
					right = mid-1;
				}else{
					left = mid+1;
				}
			}
		}
		System.out.println(arr[ml]+" "+arr[mr]);
	}
}

얻어갈 점:

• 이진 탐색 풀이 가능 이유? 이진 탐색 자체가 기본적으로 정렬된 배열로 시작해야 가능 + 전반적으로 입력되는 수들이 굉장히 큰 것에 비해 시간 제한이 1초이므로, 시간 복잡도가 낮은 탐색만 가능(logN)
• while의 조건문인 left <= right 조건 선정에서 ==을 어떻게 할 것인가 고민했는데, 둘이 같은 값이 나오더라도 해당 값을 2로 나눈 mid 설정에는 문제가 없기 때문에 <=로 해줌
• if(arr[mid] >= -arr[i])는 우변을 좌변으로 이항하면 결국 기준값과 미드값의 합이 >0인 경우와 ==0인 경우를 합친 것인데, >0인 경우는 right = mid-1이 문제가 안 되지만 ==0인 경우는 어떻게 할까 고민했음 => 어차피 처음으로 0인 값이 도출되면 if(min>sum) 조건은 더이상 실행되지 않음 => 지속적으로 탐색이어가도 결과에 영향을 미치지 않음