🥇 2230번: 수 고르기

👉🏻 2230번: 수 고르기

import sys; input=sys.stdin.readline

N, M = map(int, input().split())
num = sorted([int(input()) for _ in range(N)])

left, right = 0, 1
ans = float('inf')

while right < N:
    diff = num[right] - num[left]
    if diff < M:
        right += 1
        continue
    elif diff == M:
        ans = diff
        break
    else:
        left += 1
    ans = min(ans, diff)

print(ans)

 

---

💡 왜 이렇게 풀었을까?

• 저는 투 포인터를 사용해서 해당 문제를 풀었습니다. 이제는 왜 투 포인터를 사용하는지 알겠더군요.
• M과 A[i]의 크기 범위만 봐도 2중 반복문으로 걸러내기엔 시간 초과가 날 것만 같았습니다.
  • 투 포인터는 정렬된 상태에서 탐색하면 두 수의 차이를 조금 더 효율적으로 계산할 수 있고,
  • 그래서 특정 차이를 만족하는 두 수를 빠르게 찾기 위해 투 포인터 기법을 활용해봤습니다.
• 시간 복잡도를 따져보면, 정렬에 O(NlogN) + 투 포인터에 O(N)으로, 최대 O(N log N)으로 해결이 가능했고,
• 2중 반복문을 사용했을 때의 O(N^2)보다 훨씬 빠르게 동작합니다.
• 코드는 right를 증가시키면 차이가 커지고, left를 증가시키면 차이가 작아진다는 특징을 바탕으로 구현하였습니다.