크기가 n인 배열 A와 하나의 숫자 d가 주어졌다고 가정해 봅시다. 드림랜드(Dreamland) 군대의 규정에 따르면, 정찰 부대는 반드시 두 명의 병사로 구성되어야 합니다. 또한 두 병사의 신체 조건이 크게 차이 나지 않아야 하므로, 두 병사의 키 차이는 최대 d센티미터를 넘을 수 없습니다.
병사 n명의 키가 배열 A에 저장되어 있으며, 그중에는 키가 같은 병사도 있습니다. 우리가 구해야 할 것은 이 n명의 병사 중에서 정찰 부대를 편성할 수 있는 경우의 수입니다.
예를 들어 입력이 A = [10, 20, 50, 60, 65], d = 10이라면 출력은 6이 됩니다. 가능한 편성 조합은 (10, 20), (20, 10), (50, 60), (60, 50), (60, 65), (65, 60)으로 총 6가지이기 때문입니다.
문제 해결 접근 방법
이 문제는 다음 단계를 통해 해결할 수 있습니다.
- 결과를 저장할 변수 ans를 0으로 초기화합니다.
- 배열의 모든 서로 다른 두 인덱스 쌍 (i, j)에 대해 |A[i] - A[j]| <= d 조건을 검사합니다.
- 조건을 만족하면 ans를 1씩 증가시킵니다.
- 마지막으로 ans * 2를 반환합니다. (i, j) 쌍만 세었기 때문에 순서가 바뀐 (j, i)까지 포함하여 두 배로 만들어 주는 것입니다.
ans := 0
for initialize i := 1, when i < size of A, update (increase i by 1), do:
for initialize j := 0, when j < i, update (increase j by 1), do:
if |A[i] - A[j]| <= d, then:
(increase ans by 1)
return ans * 2C++ 구현 예제
아래의 실제 C++ 코드 구현을 통해 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> A, int d){
int ans = 0;
for (int i = 1; i < A.size(); i++)
for (int j = 0; j < i; j++)
if (abs(A[i] - A[j]) <= d)
ans++;
return ans * 2;
}
int main(){
vector<int> A = { 10, 20, 50, 60, 65 };
int d = 10;
cout << solve(A, d) << endl;
}입력
{ 10, 20, 50, 60, 65 }, 10출력
6
코드 설명
위 코드에서 solve 함수는 배열 A의 모든 두 병사 조합을 이중 반복문으로 확인합니다. 외부 루프 변수 i는 1부터 시작하고 내부 루프 변수 j는 항상 i보다 작으므로, 각 쌍은 한 번씩만 검사됩니다. 키 차이가 d 이하인 쌍을 발견할 때마다 카운트를 증가시키고, 최종적으로 결과에 2를 곱해 순서를 고려한 전체 편성 방법의 수를 반환합니다. 시간 복잡도는 O(n²)이며, 병사 수가 많지 않은 경우 충분히 효율적으로 동작합니다.