๐ ๋ฌธ์
https://www.acmicpc.net/problem/2230
๐ ์์ด๋์ด
ํฌ ํฌ์ธํฐ๋ฅผ ํ์ฉํ์ฌ ํด๊ฒฐํ์์ต๋๋ค.
์ ๋ ฌ ์ดํ์ ๋ง์ฝ ์ต๋จ ๊ฐ ๋ฒ์ ๋ณด๋ค ์๋ค๋ฉด right๋ฅผ ์ค๋ฅธ์ชฝ์ผ๋ก ์ฎ๊ฒจ์ ๋ ์์ ์ฐจ์ด๋ฅผ ๋ฒ๋ฆฌ๊ณ ๋ง์ฝ ์ต๋จ ๊ฐ ๋ฒ์๋ณด๋ค ํฌ๋ค๋ฉด ๊ธฐ์กด์ diffMin๊ฐ๊ณผ ๋น๊ตํ์ฌ ๋ ์์๊ฐ์ ๊ฐ์ง๋๋ก ์๊ธดํ๊ณ ๋ ์์ ์ฐจ์ด๋ฅผ ์ค์ด๊ธฐ ์ํด left๋ฅผ ํ์นธ ์ค๋ฅธ์ชฝ์ผ๋ก ์ฎ๊ฒผ์ต๋๋ค.
ํด๋น ๋ฐฉ๋ฒ ํ์ด๋ฅผ ์๊ฐ์ ๋น๊ตํด๋ณด๋ ์๋๊ฐ ๋ค๋ฅธ ๋ถ๋ค๋ณด๋ค ์กฐ๊ธ ๋ ๋ฆ์๊ฒ์ ํ์ธํ ์ ์์์ต๋๋ค.
์ด ๋ถ๋ถ์ ๋ง์ฝ ๋์์ ์ฐจ์ด๊ณผ M์ธ ๊ฒฝ์ฐ ํด๋น ์ฐจ์ด๊ฐ ๊ฐ์ฅ ์์ ๊ฒฝ์ฐ์ด๊ธฐ ๋๋ฌธ์ ๋ฐ๋ก์ ์งํ ์ ์๋ค๋๊ฒ์ ์ถ๊ฐํ ์ ์์ต๋๋ค.
๋ํ ํด๋น ๋ ์๋ฅผ ์ ํํ๋๊ฒฝ์ฐ ๊ฐ์ ์๋ฅผ ๊ณ ๋ฅผ์๋ ์๋ค๋ ์ ๋ ํ์ธํด์ผํฉ๋๋ค.
๐ ํ์ด
package ๋ฐฑ์ค.twoPointer;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;
public class Boj_2230_์๊ณ ๋ฅด๊ธฐ {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int diffMin = Integer.parseInt(st.nextToken());
List<Integer> arrs = new ArrayList<>();
for (int i = 0; i < a; i++) {
arrs.add(Integer.parseInt(br.readLine()));
}
Collections.sort(arrs);
int min = Integer.MAX_VALUE;
int left = 0;
int right = 0;
while (left < a && right < a) {
int abs = Math.abs(arrs.get(left) - arrs.get(right));
if (abs < diffMin) {
right++;
} else {
min = Math.min(min, abs);
left++;
}
}
System.out.println(min);
}
}
'๋ฐฑ์ค(boj)' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[JAVA]5427 ๋ถ ๊ณจ๋4 (0) | 2023.08.21 |
---|---|
[JAVA]2531 ํ์ ์ด๋ฐฅ (0) | 2023.08.10 |
[JAVA]11780 ํ๋ก์ด๋, ํ๋ก์ด๋ ์์ (1) | 2023.08.09 |
[JAVA]๋ฐฑ์ค 13335 ํธ๋ญ Deque, queue (0) | 2023.07.31 |
[JAVA]18869 ๋ฉํฐ๋ฒ์ค2 , ์ขํ์์ถ (0) | 2023.07.28 |