문제

BOJ 2230: 수 고르기 https://www.acmicpc.net/problem/2230

풀이

조건

• N개의 정수로 이루어진 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구한다.

풀이 순서

1. 이분 탐색

• 숫자 하나를 기준으로 문제 조건에 맞는 값을 찾는 방식으로 해결했다.
• 이 때 시간복잡도를 고려해 이분 탐색을 사용했다.
• 입력 받은 값을 정렬한다.
• 이분 탐색을 통해 Lower Bound를 찾아 그 중 최소값을 구했다.

2. 투 포인터

• 입력 받은 값을 정렬한다.
• 작은 쪽(앞 쪽) 인덱스를 가리키는 포인터: s
• 큰 쪽(뒤 쪽) 인덱스를 가리키는 포인터: e
• e가 범위를 벗어나지 않고 s가 e를 넘어서지 않을 때 까지 반복문을 수행한다.
• s와 e가 가리키는 값의 차이를 구한다.
  • 그 차이가 M 이상이면 s만 +1 해주고, 그 차이값들의 최소값을 구한다.
  • 그 차이가 M 미만이면 e만 +1 해준다.

코드

Java

1. 이분 탐색

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

public class Main {
	
	static int N, M;
	static int[] arr;
	
	static int answer;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		// 수 입력
		arr = new int[N];
		for(int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		
		// 이분탐색을 위해 정렬
		Arrays.sort(arr);
		// answer 초기화
		answer = Integer.MAX_VALUE;
		
		// 수 1개 고름
		for(int i = 0; i < N; i++) {
			// 목표값 설정
			int target = arr[i] + M;
			// 목표값이 가장 큰 값보다 크면 더이상 탐색 안해도 됨
			if(target > arr[N - 1]) break;
			
			// 이분탐색 시작
			binarySearch(i);
			
			// 구한 답이 M과 같으면 그 값이 최소값(정답)이므로 더이상 탐색 안해도 됨
			if(answer == M) {
				break;
			}
		}
		
		System.out.println(answer);
	}
	
	// 이분탐색으로 목표 값 찾기
	// Lower Bound 방식 사용
	static void binarySearch(int start) {
		int s = start;
		int e = N;
		
		while(s < e) {
			int mid = (s + e) / 2;
			
			// 탐색한 값과 입력받은 값의 차이가 M보다 작으면 더 큰 값을 찾아야 됨
			if(arr[mid] - arr[start] < M) {
				s = mid + 1;
			} 
			// 탐색한 값과 입력받은 값의 차이가 M 이상이면 더 작은 값을 찾아야 됨
			else {
				e = mid;
			}
		}
		
		// 탐색이 끝난 뒤 e가 아직 N이라면
		// 두 값의 차이가  계속 M보다 작다는 의미
		// 문제 조건과 유효하지 않은 경우이므로 바로 종료
		if(e == N) {
			return;
		}
		
		// 유효한 경우라면 최소값 찾기
		answer = Math.min(answer, arr[e] - arr[start]);	
	}

}

2. 투 포인터

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

public class Main {
	
	static int N, M;
	static int[] arr;
	
	static int answer;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		// 수 입력
		arr = new int[N];
		for(int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		// 정렬
		Arrays.sort(arr);
		
		int answer = Integer.MAX_VALUE;
		
		int s = 0; // 작은 쪽 포인터
		int e = 0; // 큰 쪽 포인터
		// 끝날 때 까지 반복
		while(e < N && s <= e) {
			int rst = arr[e] - arr[s]; // 두 포인터가 가리키는 값의 차
			// 두 값의 차이가 M 이상이면
			// s++, 그 차이의 최소값 구하기
			if(rst >= M) {
				s++;
				answer = Math.min(answer, rst);
			} 
			// 두 값의 차이가 M보다 작으면 e++
			else {
				e++;
			}
		}
		
		System.out.println(answer);
	}

}

정리

• 이분탐색과 투 포인터 두 가지 방법으로 해결했다.