정수 n개 a₁ … aₙ과 정수 k가 주어진다. 두 자리 i < j 가운데 |aᵢ − aⱼ| ≤ k인 것이 몇 쌍인지 출력하라. 값이 같아도 자리가 다르면 다른 수로 친다. 같은 두 자리를 순서만 바꾼 것(i, j와 j, i)은 한 쌍이다. n = 1이면 답은 0이다. 첫 줄에 n과 k가, 둘째 줄에 a₁ … aₙ이 빈칸으로 나뉘어 주어진다.
5 3 1 9 4 7 3
5
2 1000000000 -2000000000 2000000000
0
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
두 수를 모두 짝지어 보면 n²/2 = 5천만 번이라 크레이콘은 실행 걸음 한도(약 5천만)를 넘고 Python도 느려요.
정렬하면 a[j]와 차이가 k 이하인 수는 a[j] 바로 앞의 한 구간 a[i..j−1]이 되고, j가 오른쪽으로 갈수록 i도 오른쪽으로만 가요(두 포인터).
그래서 정렬 n log n + 훑기 2n이면 끝나요.
정렬은 언어마다 달라요.
Python sorted(), Java Arrays.sort(), C# Array.Sort(), C++ std::sort는 수를 크기 차례로 늘어놓아요.
크레이콘 a.정렬()도 기준 함수를 빼면 수는 작은 것부터예요.
하지만 JavaScript·TypeScript의 sort()는 비교 함수를 넘기지 않으면 문자열로 바꿔 사전 순으로 늘어놓아서 10이 9보다, -1이 -2보다 앞에 와요 — a.sort((x, y) => x - y)처럼 함수를 넘겨요.
C의 qsort도 비교 함수를 함수 포인터로 받는데, 흔히 쓰는 return x - y;는 2×10⁹ − (−2×10⁹)에서 int를 넘쳐 차례가 뒤집혀요 — (x > y) - (x < y)로 크기만 비교해요.
같은 넘침이 두 포인터의 a[j] - a[i]에도 있어요: 차이가 4×10⁹까지라 Java·C#·C·C++는 long/long long으로 바꿔 빼야 하고, 안 그러면 예시 2가 1이 나와요.
그리고 '이하'라서 > k일 때만 i를 옮겨요 — >= k로 옮기면 k = 0일 때 같은 값끼리의 쌍을 놓쳐요.
n, k = map(int, input().split())a = sorted(map(int, input().split())) # 정렬하면 a[j]와 차이가 k 이하인 것은 a[j] 바로 앞의 한 구간이다.# j가 오른쪽으로 갈수록 구간의 왼쪽 끝 i도 오른쪽으로만 간다(두 포인터).count = 0i = 0for j in range(n): while a[j] - a[i] > k: i += 1 count += j - i # a[i..j-1]이 모두 짝이 된다print(count)const [n, k, ...a] = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);// sort()에 비교 함수를 넘기지 않으면 문자열로 바꿔 사전 순으로 늘어놓는다(10이 9보다 앞)a.sort((x, y) => x - y); // a[j]와 차이가 k 이하인 것은 a[j] 바로 앞의 한 구간이다. 왼쪽 끝 i는 오른쪽으로만 간다.let count = 0;let i = 0;for (let j = 0; j < n; j++) { while (a[j] - a[i] > k) i++; count += j - i;}console.log(count);import { readFileSync } from "node:fs"; const [n, k, ...a]: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);// sort()에 비교 함수를 넘기지 않으면 문자열로 바꿔 사전 순으로 늘어놓는다(10이 9보다 앞)a.sort((x: number, y: number): number => x - y); // a[j]와 차이가 k 이하인 것은 a[j] 바로 앞의 한 구간이다. 왼쪽 끝 i는 오른쪽으로만 간다.let count = 0;let i = 0;for (let j = 0; j < n; j++) { while (a[j] - a[i] > k) i++; count += j - i;}console.log(count);import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(in.readLine()); int n = Integer.parseInt(st.nextToken()); int k = Integer.parseInt(st.nextToken()); int[] a = new int[n]; st = new StringTokenizer(in.readLine()); for (int i = 0; i < n; i++) a[i] = Integer.parseInt(st.nextToken()); Arrays.sort(a); // a[j]와 차이가 k 이하인 것은 a[j] 바로 앞의 한 구간이다. 왼쪽 끝 i는 오른쪽으로만 간다. long count = 0; int i = 0; for (int j = 0; j < n; j++) { while ((long) a[j] - a[i] > k) i++; // 차이는 4×10⁹까지라 long으로 뺀다 count += j - i; } System.out.println(count); }}using System;using System.Linq; class Program{ static void Main() { string[] first = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); int n = int.Parse(first[0]); long k = long.Parse(first[1]); long[] a = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries).Select(long.Parse).ToArray(); Array.Sort(a); // a[j]와 차이가 k 이하인 것은 a[j] 바로 앞의 한 구간이다. 왼쪽 끝 i는 오른쪽으로만 간다. long count = 0; int i = 0; for (int j = 0; j < n; j++) { while (a[j] - a[i] > k) i++; // long이라 4×10⁹ 차이도 넘치지 않는다 count += j - i; } Console.WriteLine(count); }}#include <algorithm>#include <iostream>#include <vector> int main() { int n; long long k; std::cin >> n >> k; std::vector<long long> a(n); for (long long& x : a) std::cin >> x; std::sort(a.begin(), a.end()); // a[j]와 차이가 k 이하인 것은 a[j] 바로 앞의 한 구간이다. 왼쪽 끝 i는 오른쪽으로만 간다. long long count = 0; int i = 0; for (int j = 0; j < n; j++) { while (a[j] - a[i] > k) i++; count += j - i; } std::cout << count << "\n";}#include <stdio.h>#include <stdlib.h> static int a[10000]; /* qsort에 넘기는 비교 함수. x - y로 돌려주면 int를 넘칠 수 있어서 크기만 비교한다. */static int ascending(const void* p, const void* q) { int x = *(const int*)p, y = *(const int*)q; return (x > y) - (x < y);} int main(void) { int n, k; scanf("%d %d", &n, &k); for (int i = 0; i < n; i++) scanf("%d", &a[i]); qsort(a, n, sizeof a[0], ascending); /* a[j]와 차이가 k 이하인 것은 a[j] 바로 앞의 한 구간이다. 왼쪽 끝 i는 오른쪽으로만 간다. */ long long count = 0; int i = 0; for (int j = 0; j < n; j++) { while ((long long)a[j] - a[i] > k) i++; /* 차이는 4×10⁹까지 */ count += j - i; } printf("%lld\n", count); return 0;}첫줄 = 콘솔.수들읽기();n = 첫줄[0];k = 첫줄[1];a = 콘솔.수들읽기();// 기준 함수를 주지 않으면 수는 작은 것부터 늘어놓는다a.정렬(); // a[j]와 차이가 k 이하인 것은 a[j] 바로 앞의 한 구간이다. 왼쪽 끝 i는 오른쪽으로만 간다.count = 0;i = 0;반복 (j = 0; j < n; j++){ 동안 (a[j] - a[i] > k) { i += 1; } count += j - i;}콘솔.쓰기(count);