n개의 요소를 가진 배열 A가 있다고 가정해 봅시다. 어느 전자 제품 매장에서 지난밤 도난 사건이 발생했습니다. 매장에 있던 모든 키보드는 특정 정수 x부터 시작하여 오름차순으로 번호가 매겨져 있었습니다.
예를 들어 x=4이고 매장에 키보드가 3개 있었다면, 기기들의 번호는 4, 5, 6이 됩니다. 마찬가지로 x=10이고 키보드가 7개였다면 번호는 10, 11, 12, 13, 14, 15, 16입니다. 도난 사건 이후에는 n개의 키보드만 남았으며, 남아 있는 키보드들의 번호가 배열 A에 저장되어 있습니다. 우리가 구해야 할 것은 바로 도난당한 키보드의 최소 개수입니다.
예를 들어 입력이 A = [10, 13, 12, 8]이라면 출력은 2가 됩니다. x = 8이라고 가정하면, 전체 키보드 번호는 8부터 13까지 존재하고 그중 9번과 11번 두 개가 도난당했기 때문입니다.
문제 해결 접근 방식
이 문제의 핵심 아이디어는 다음과 같습니다. 키보드 번호는 x부터 연속적으로 매겨졌으므로, 남아 있는 키보드 중 최솟값(A[0])부터 최댓값(A[n-1])까지의 범위 안에 원래 존재했던 키보드의 수가 포함됩니다. 따라서 다음 공식을 사용할 수 있습니다.
전체 범위의 키보드 수 = A[n-1] - A[0] + 1
도난당한 키보드 수 = 전체 범위의 키보드 수 - 남아 있는 키보드 수(n)
즉, 배열을 먼저 정렬한 뒤 최댓값과 최솟값의 차이에 1을 더하고, 남아 있는 개수 n을 빼주면 도난당한 키보드의 최소 개수를 구할 수 있습니다.
알고리즘 단계
이 문제를 해결하기 위해 다음 단계를 따릅니다 −
배열 A를 오름차순으로 정렬한다
n := 배열 A의 크기
return A[n - 1] - A[0] + 1 - n
C++ 구현 예제
아래 구현 예제를 통해 더 잘 이해해 봅시다 −
#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> A) {
sort(A.begin(), A.end());
int n = A.size();
return A[n - 1] - A[0] + 1 - n;
}
int main() {
vector<int> A = { 10, 13, 12, 8 };
cout << solve(A) << endl;
}
입력
{ 10, 13, 12, 8 }출력
2
복잡도 분석
이 알고리즘의 시간 복잡도는 배열 정렬에 의해 결정되므로 O(n log n)입니다. 정렬 대신 한 번의 순회로 최댓값과 최솟값을 직접 찾으면 시간 복잡도를 O(n)까지 줄일 수 있습니다. 공간 복잡도는 추가 메모리를 거의 사용하지 않으므로 O(1)입니다.