n개의 원소를 가진 배열 A가 있다고 가정해 보겠습니다. 우리는 주어진 숫자 중 임의의 부분 집합을 골라 해당 숫자들의 부호를 반전(음수화)할 수 있습니다. 이때 배열에서 만들어낼 수 있는 서로 다른 값의 최대 개수를 구하는 것이 문제입니다.
예를 들어 입력이 A = [1, 1, 2, 2]라고 한다면, 출력은 4가 됩니다. 첫 번째 원소와 마지막 원소의 부호를 반전하면 [-1, 1, 2, -2]라는 배열을 만들 수 있고, 이 배열은 네 개의 서로 다른 값(-1, 1, 2, -2)을 가지기 때문입니다.
문제 해결 아이디어
핵심은 각 숫자를 집합(set)에 삽입할 때, 같은 값이 이미 존재한다면 그 음수 형태를 추가로 넣는 것입니다. 어떤 절댓값이 두 번 이상 등장하면 하나는 양수로, 다른 하나는 음수로 만들 수 있으므로, 결과적으로 더 많은 서로 다른 값을 확보할 수 있습니다.
알고리즘 단계
다음 순서대로 문제를 해결할 수 있습니다.
- 정수를 저장할 집합(set)
se를 하나 정의합니다. n := 배열 A의 크기로 설정합니다.- i를 0부터 n-1까지 반복하며 다음을 수행합니다.
x := A[i]- x가
se에 이미 존재하면-x를se에 삽입합니다. - 그렇지 않으면
x를se에 삽입합니다.
- 마지막으로
se의 크기를 반환합니다.
집합은 중복을 허용하지 않으므로, 위 과정이 끝나면 집합에는 만들 수 있는 모든 서로 다른 값이 저장되게 됩니다.
C++ 구현 예제
아래 코드를 통해 동작 방식을 더 명확히 이해할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> A) {
set<int> se;
int n = A.size();
for (int i = 0; i < n; i++) {
int x = A[i];
if (se.count(x))
se.insert(-x);
else
se.insert(x);
}
return se.size();
}
int main() {
vector<int> A = { 1, 1, 2, 2 };
cout << solve(A) << endl;
}입력
{ 1, 1, 2, 2 }출력
4
동작 과정 살펴보기
예제 입력 [1, 1, 2, 2]에 대해 알고리즘이 어떻게 진행되는지 단계별로 확인해 보겠습니다.
- 첫 번째 1 → 집합에 없으므로
1삽입 → se = {1} - 두 번째 1 → 이미 존재하므로
-1삽입 → se = {-1, 1} - 첫 번째 2 → 없으므로
2삽입 → se = {-1, 1, 2} - 두 번째 2 → 이미 존재하므로
-2삽입 → se = {-2, -1, 1, 2}
최종적으로 집합의 크기인 4가 반환되며, 이는 부호 반전을 통해 얻을 수 있는 서로 다른 값의 최대 개수와 일치합니다.
시간 복잡도
각 원소마다 집합 탐색 및 삽입 연산이 한 번씩 수행되므로, 전체 시간 복잡도는 O(n log n)입니다. 여기서 n은 배열의 크기이며, log 항은 std::set이 내부적으로 균형 이진 탐색 트리를 사용하기 때문에 발생합니다.