문제
누적 합 형태의 배열이 주어질 때, 각 구간에 해당하는 값의 개수만큼 구간 번호를 반복 출력하는 문제
풀이
누적 합 배열에서 인접한 두 값의 차이가 해당 구간의 원소 수이다. p[i] - p[i-1]만큼 구간 번호 i를 반복 출력한다.
코드
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int k;
while (cin >> k && k != 0) {
vector<int> p(k + 1, 0);
for (int i = 1; i <= k; ++i) {
cin >> p[i];
}
for (int i = 1; i <= k; ++i) {
int count = p[i] - p[i - 1];
for (int j = 0; j < count; ++j) {
cout << i << " ";
}
}
cout << "\n";
}
return 0;
}복잡도
- 시간: O(N) (N: 총 원소 수)
- 공간: O(K) (K: 구간 수)