문제
문제
N의 정수로 이루어진 수열 A[1], A[2], ... A[N]이 있다. 이 수열에서 두 수(같은 수일 수도 있음)를 골랐을 때 그 차이가 M 이상이면서 제일 작은 경우를 출력하라.
시간 제한 : 2초
메모리 제한 : 128MB
입력
N M
arr[0]
arr[1]
...
arr[N]
풀이
순차적인 자료 구조(array)를 사용할 때 포인터를 옮겨가며 답을 찾을 수 있을 것 같아 투 포인터 알고리즘을 사용하기로 했다. start = 0, end = length-1로 잡아야 할지, start = 0, end = 0으로 잡아야 할지를 고민했다.
start = 0, end = length-1 이면
M보다 클 때 end를 줄일 것이다. (end를 줄여야 M보다 작은 수가 나올 테니까)
생각해보면 아래와 같은 반례를 금방 떠올릴 수 있었다.
N = 5, M = 2
arr = 1 2 7 7 8 13
처음엔 end = 5고 start = 0이니까 10-1 = 9
여기서 점점 end를 줄여가다보면...
답은 13-7 혹은 7-1한 6이다
13-1 = 12
8-1 = 7
7-1 = 6
2-1 = 1 > M => start를 늘린다?
이러면 start == end니까 end++ start++...?
비효율적이다...
그리고 건너뛰는 숫자가 없어야 하는데, 위와 같은 방법으로는 건너뛰게 되는 값들이 생긴다.
그래서 start = 0, end = 0일 때로 구현해보았다.
생각한 플로우는 다음과 같다.
arr[end] - arr[start] < M ⇒ end++
arr[end] - arr[start] > M ⇒ start++
if start end ⇒ end++
if start - end M ⇒ return(더 찾을 필요 X)
위의 플로우에 따라 작성한 코드는 이렇다.
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int[] arr = new int[N];
for(int i = 0; i<N; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
Arrays.sort(arr);
int res = Integer.MAX_VALUE;
int start = 0;
int end = 1;
while(end<N) {
int diff = arr[end] - arr[start];
if(diff == M) {
System.out.println(M);
return;
} else if(diff > M) {
start++;
res = Math.min(res, diff);
} else {
end++;
}
if(end == start) {
end++;
}
}
System.out.println(res);
}
}문제를 풀며
특정 값을 찾는 문제라면 end = length-1로 시작하는 게 낫다는 걸 깨닫게 됐다.
왜냐면 조건에 따라 end를 줄이고 start를 늘리다보면 건너뛰게 되는 쌍이 있을 것이기 때문에... (1,n) (2,n) (3,n) ... (n-1, n) 이렇게 모든 쌍들을 일일히 확인하고 넘어가게 되는 게 아니라, (1, n) (2, n) (3, n-1) (3, n-2) 이런 식으로 조건에 만족하는 범위 내로만 탐색하므로 건너뛰게 되는 쌍들이 존재한다.
알고리즘은 애플리케이션에서 어떻게 돌아갈지와 스스로 반례를 찾아낼 때 제일 재미있는 것 같다🤓 뇌에 쥐 나는 감각 ㅎㅎ