서로 다른 n개의 요소로 구성된 배열 A가 있다고 가정해 봅시다. 배열 B가 nice(좋은 배열)라고 불리려면 다음 조건을 만족해야 합니다.
- 서로 다른 임의의 두 요소 B[i]와 B[j]에 대해 그 차이의 절댓값 |B[i] - B[j]|가 반드시 배열 B 안에 적어도 한 번 존재해야 합니다.
- 배열 B의 모든 요소는 중복 없이 서로 달라야 합니다.
우리의 목표는 배열 A에 여러 개의 정수를 추가하여 크기가 최대 300인 nice 배열을 만들 수 있는지 확인하는 것입니다. 가능하다면 새로운 배열을 반환하고, 불가능하다면 -1을 반환합니다.
입력 예시
예를 들어 입력이 A = [4, 8, 12, 6]라고 해보겠습니다. 이 경우 출력은 [8, 12, 6, 2, 4, 10]이 될 수 있습니다.
이유는 다음과 같습니다.
- |4−2| = |6−4| = |8−6| = |10−8| = |12−10| = 2 → 2는 배열 안에 존재
- |6−2| = |8−4| = |10−6| = |12−8| = 4 → 4는 배열 안에 존재
- |8−2| = |10−4| = |12−6| = 6 → 6은 배열 안에 존재
- |10−2| = |12−4| = 8 → 8은 배열 안에 존재
- |12−2| = 10 → 10은 배열 안에 존재
따라서 이 배열은 nice 배열입니다. 물론 다른 정답도 가능합니다.
해결 방법 및 접근 방식
이 문제를 해결하기 위한 핵심 아이디어는 간단합니다. 만약 배열에 음수가 하나라도 포함되어 있다면, 어떻게 정수를 추가하더라도 nice 배열을 만들 수 없으므로 -1을 출력합니다. 음수가 없다면, 0부터 배열의 최댓값까지 모든 정수를 포함하는 배열을 만들면 됩니다.
왜 이 방법이 동작할까요? 0부터 b까지 연속된 정수로 구성된 배열에서 임의의 두 요소 x, y(x < y)를 선택하면, 그 차이 y − x 역시 0과 b 사이의 값이므로 반드시 배열 안에 존재하기 때문입니다.
알고리즘 단계
n := 배열 A의 크기
t := 0
b := 0
i := 0부터 i < n까지 반복:
a := A[i]
만약 a < 0이면:
t := 1
b := max(a, b)
만약 t가 0이 아니면:
-1 출력
그렇지 않으면:
i := 0부터 i <= b까지 반복하며 i 출력C++ 코드 구현
아래는 위 알고리즘을 구현한 C++ 코드입니다.
#include <bits/stdc++.h>
using namespace std;
void solve(vector<int> A) {
int n = A.size();
int t = 0;
int b = 0;
for (int i = 0; i < n; i++) {
int a = A[i];
if (a < 0)
t = 1;
b = max(a, b);
}
if (t)
cout << "-1";
else {
for (int i = 0; i <= b; i++)
cout << i << ", ";
}
}
int main() {
vector<int> A = { 4, 8, 12, 6 };
solve(A);
}입력
{ 4, 8, 12, 6 }출력
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12,
코드 설명
- 먼저 배열 A를 순회하면서 음수가 있는지 확인합니다(t 플래그 사용).
- 동시에 순회 과정에서 배열의 최댓값 b를 구합니다.
- 음수가 발견되면 nice 배열을 만들 수 없으므로 -1을 출력합니다.
- 음수가 없다면 0부터 최댓값 b까지 모든 정수를 순서대로 출력합니다. 이 배열은 크기가 b + 1이며, 문제 조건인 300 이하를 만족하는 경우에만 유효한 답이 됩니다.
이 알고리즘의 시간 복잡도는 O(n + b)로, 배열 순회와 결과 출력에 비례하여 매우 효율적입니다.