📌 문제 정보

링크: https://www.acmicpc.net/problem/2230

유형: 정렬, 투포인터

난이도: 골드5

스스로 풀었는가? ✅

💻 작성 코드

import sys

readline = sys.stdin.readline

N, M = map(int, readline().split())
numbers = []
for i in range(N):
    numbers.append(int(readline()))

numbers.sort()

start_idx = 0
end_idx = 0
min_diff = sys.maxsize
while end_idx < N:
    diff = numbers[end_idx] - numbers[start_idx]
    if diff == M:
        min_diff = min(min_diff, diff)
        end_idx += 1
    elif diff > M:
        min_diff = min(min_diff, diff)
        start_idx += 1
    else:
        end_idx += 1

print(min_diff)

🎯 접근 방식

1. 수열에서 두 수를 고르기만 하면 되므로 먼저 수열을 정렬한다.
2. 차이(diff)가 목표값(M)보다 크면 start_idx 늘리고, 목표보다 작으면 end_idx 늘리고, 목표와 같으면 end_idx 늘린다.
3. 차이가 M 이상이면서 제일 작은 경우를 구해야 하므로 diff가 M 이상이라면 diff와 min_diff 값을 비교한다.

💡 개선사항

1. 차이가 M 이상이면서 제일 작은 경우를 구하기 때문에, diff == M이라면 바로 반복문을 종료해도 된다.

[ktb-algorithm-study] 1주차