문제
N(1≤N≤100,000)개의 수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오.
예를 들어 수열이 {1, 2, 3, 4, 5}라고 하자. 만약 M=3일 경우, 1 4, 1 5, 2 5를 골랐을 때 그 차이가 M 이상이 된다. 이 중에서 차이가 가장 작은 경우는 1 4나 2 5를 골랐을 때의 3이 된다.
입력
첫째 줄에 두 정수 N, M(0≤M≤2,000,000,000)이 주어진다. 다음 N개의 줄에는 차례로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0 ≤ |A[i]| ≤ 1,000,000,000을 만족한다.
출력
첫째 줄에 M 이상이면서 가장 작은 차이를 출력한다. 항상 차이가 M이상인 두 수를 고를 수 있다.
코드
#include <iostream> #include <algorithm> #include <array> using namespace std; array<int, 100'000> A; int N, M; int Ans = 2'000'000'001; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin >> N >> M; for (int i = 0; i < N; ++i) cin >> A[i]; // 오름차순으로 정렬한다. sort(A.begin(), A.begin() + N); // 처음부터 하나하나 비교해가며 답을 찾는다. int left = 0; for (int right = 0; left < N && right < N;) { int diff = A[right] - A[left]; if (diff >= M) { Ans = min(Ans, diff); ++left; } else ++right; } cout << Ans; } |
using System; namespace ForAlgoCsharp { class Program { static int N, M, Ans = 2000000001; static int[] A = new int[100000]; static void Main(string[] args) { string[] inputs = Console.ReadLine().Split(); N = Convert.ToInt32(inputs[0]); M = Convert.ToInt32(inputs[1]); for (int i = 0; i < N; ++i) A[i] = Convert.ToInt32(Console.ReadLine()); Array.Sort(A, 0, N); int left = 0, right = 0; while (left < N && right < N) { int diff = A[right] - A[left]; if (diff >= M) { Ans = Math.Min(Ans, diff); ++left; } else ++right; } Console.Write($"{Ans}"); } } } |
from sys import stdin, stdout input = stdin.readline print = stdout.write N, M = map(int, input().split()) A = sorted([int(input()) for i in range(N)]) Ans = 2000000001 left, right = 0, 0 while (left < N and right < N): diff = A[right] - A[left] if (diff >= M): Ans = min(Ans, diff) left += 1 else: right += 1 print(f'{Ans}') |
복기
너무 복잡하게 생각하지 말자.