n개의 양의 정수로 이루어진 배열 A가 있다고 가정해 봅시다. 이 배열에 다음과 같은 연산을 반복해서 적용합니다.
연산 규칙: 서로 값이 다른 인접한 두 요소를 제거하고, 그 자리에 두 요소의 합을 넣습니다. 이 연산을 수행할 때마다 배열의 크기는 1씩 줄어듭니다.
우리가 구해야 할 것은 이러한 연산을 원하는 만큼 수행한 후, 배열이 가질 수 있는 최소 길이입니다.
예시
입력이 다음과 같다고 해보겠습니다.
A = [2, 1, 3, 1]
이 경우 출력은 1이 됩니다. 그 과정은 다음과 같습니다.
먼저 (1, 3)을 선택해 합치면 배열은 [2, 4, 1]이 됩니다. 다음으로 (2, 4)를 선택하면 [6, 1]이 되고, 마지막으로 남은 두 요소를 합치면 [7]이 되어 배열의 길이는 1이 됩니다.
해결 접근 방식
이 문제는 사실 매우 간단한 관찰 하나로 해결할 수 있습니다.
- 배열 안에 서로 다른 값이 두 개 이상 존재한다면, 적절히 인접한 서로 다른 요소들을 계속 병합하여 결국 배열을 길이 1까지 줄일 수 있습니다.
- 반대로 배열의 모든 요소가 같은 값으로만 이루어져 있다면, 어떤 두 요소도 '서로 다르다'는 조건을 만족하지 못하므로 아무런 연산도 수행할 수 없습니다. 따라서 배열의 길이는 n 그대로 유지됩니다.
따라서 알고리즘은 다음과 같습니다.
- 배열의 고유한 값들을 집합(set)에 저장합니다.
- 집합의 크기가 1이라면(모든 요소가 동일하다면) n을 반환합니다.
- 그렇지 않다면 1을 반환합니다.
C++ 구현 코드
아래는 위 로직을 C++로 구현한 예제입니다.
#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> A) {
int n = A.size();
set<int> a;
for (int i = 0; i < n; i++) {
a.insert(A[i]);
}
if (a.size() == 1)
return n;
else
return 1;
}
int main() {
vector<int> A = { 2, 1, 3, 1 };
cout << solve(A) << endl;
}입력
{ 2, 1, 3, 1 }출력
1
복잡도 분석
시간 복잡도는 배열을 한 번 순회하며 집합에 값을 삽입하므로 O(n log n)이며, 공간 복잡도는 고유한 값을 저장하기 위한 O(n)입니다. 전체 배열을 실제로 시뮬레이션하지 않고도 답을 즉시 판단할 수 있는 효율적인 방법입니다.