https://www.acmicpc.net/problem/2230
사용 알고리즘
- 투 포인터
풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static int n, m;
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());
int [] arr = new int[n];
int min = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
Arrays.sort(arr);
int hi = 0;
for(int lo = 0; lo < n; lo++) {
while(hi < n && Math.abs(arr[hi] - arr[lo]) < m) {
hi++;
}
if (hi == n) break;
min = Math.min(min, Math.abs(arr[hi] - arr[lo]));
}
System.out.println(min);
}
}
회고
Arrays.sort의 시간 복잡도는 O(nlogn)이고, n이 10만일 때도 충분히 제한 시간인 2초 안에 통과 가능하다.
투포인터 방식으로 풀었는데, 처음에 Math.abs(arr[hi] - arr[lo])의 값이 처음 m 이상일 때 루프를 빠져나와서 다른 경우의 수를 계산해주지 못하는게 아닐까 고민이 많았다.
ex) [1,2,3,4,5] 이고 m = 3일 때, [1,4]인 경우 루프를 탈출하고 [1,5]는 계산하지 않음.
그런데, 문제에서 찾는 것은 가장 차이가 작은 경우 이므로 뒤에 [1,5]는 굳이 계산을 할 필요가 없었다!! 하지만, 이렇게 계산을 하기 위해선 반드시 오름차순으로 정렬이 되어있어야 한다. 정렬을 하지 않고 제출했을 때 문제가 틀리는 것을 확인할 수 있었다.
'Algorithm > 백준' 카테고리의 다른 글
[백준] Gold IV. 부분 합 (0) | 2024.07.21 |
---|---|
[백준] Gold V. 두 용액 (0) | 2024.07.20 |
[백준] Gold IV. 합이 0 (0) | 2024.07.20 |
[백준] Gold V. 가장 긴 짝수 연속한 부분 수열 (large) (0) | 2024.07.19 |
[백준] Silver I. 겹치는 건 싫어 (0) | 2024.07.19 |