[백준] 2230 - 수 고르기

1. 문제

2230번: 수 고르기

2. 개요

수열 A에서 두 수를 골랐을 때, 그 차가 M이상이면서 가장 작은 경우를 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

수열의 원소들을 모두 입력받고 오름차순으로 정렬한다.

좌측 포인터 l, 우측 포인터 r을 설정하고 포인터가 가리키는 인덱스의 두 수의 차 tmp를 계산한다.

tmp < M이라면 r을 한칸 우측으로 이동시켜 더 큰 값이 나오도록 한다.

tmp ≥ M이라면 이미 저장된 answer과 비교해 더 작다면 교체한다.

또한 nums[r] - nums[l]의 최솟값이 나온 경우이므로 바로 l을 이동시킨다.

l이 r을 넘거나 r 또는 l이 수열의 범위를 넘어갈 때 까지 탐색한 후, 답을 출력한다.

3-2. Python

import sys

N, M = map(int, sys.stdin.readline().split())

nums = []

for i in range(N):
    nums.append(int(sys.stdin.readline()))

nums.sort()

l, r = 0, 1
answer = 20000000000

while r < N and l < N and l <= r:
    tmp = nums[r] - nums[l]
    if tmp < M:
        r += 1
    else:
        if tmp < answer:
            answer = tmp
        l += 1

print(answer)

3-3. C#

static void Main(string[] args)
        {
            string[] input = Console.ReadLine().Split();
            int N = int.Parse(input[0]);
            int M = int.Parse(input[1]);
            int answer = int.MaxValue;

            List<int> nums = new List<int>();

            for (int i = 0; i < N; i++)
                nums.Add(int.Parse(Console.ReadLine()));

            nums.Sort();
            int l = 0;
            int r = 0;

            while (l < N && r < N && l <= r)
            {
                int tmp = nums[r] - nums[l];

                if (tmp < M)
                    r++;
                else
                {
                    if (tmp < answer)
                        answer = tmp;
                    l++;
                }
            }
            Console.WriteLine(answer);
        }