[백준] 2230번 : 수 고르기

2230번: 수 고르기

2230번: 수 고르기

🤔 문제분석

이분탐색을 이용하여 문제를 해결하였습니다.

내림차순으로 정렬한뒤에 원소를 순회하는데 순회 하고자 하는 위치 +1 부터 마지막 원소까지 이분탐색으로 mid 값을 조정하여 최소 M값을 찾아냅니다.

M값보다 크거나 같을경우 최소값을 갱신하고 end 값을 mid - 1로 지정하여 더 작은 값을 찾아냅니다. 반대로 M보다 작을경우 start를 mid +1로 지정하여 M보다 큰 값을 찾게 만듭니다.

💻 코드

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
A = []
for _ in range(N):
    A.append(int(input()))
    
A.sort()

min_value = sys.maxsize

for i in range(N):
    start = i + 1
    end = N - 1
    while end >= start:
        mid = (start + end) // 2
        cost = A[mid] - A[i]
        if cost >= M:
            min_value = min(min_value, cost)
            end = mid - 1
        else:
            start = mid + 1
            
print(min_value)

🎯 피드백 및 개선사항

투포인터를 활용하여 문제를 풀 수 도 있습니다. 내림차순으로 정렬한뒤에 left = 0, right = 1로 둔뒤에 arr[left] + arr[right] 가 M보다 크거다 같을경우 left를 증가시키고, M보다 작을경우 right 값을 증가시켜 M값보다 크게 만들어줍니다.

투포인터를 활용하면 이분탐색보다 더 빠른 O(N)으로 문제를 해결 할 수 있습니다.

import sys
input = sys.stdin.readline

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

arr.sort()
left = 0; right = 1
ans = sys.maxsize

while right != len(arr) and left != len(arr):
    tmp = arr[right] - arr[left]
    if tmp >= M:
        if ans > tmp:
            ans = tmp
        left += 1
    else:
        right += 1

print(ans)