문제
C++ std::vector 같은 동적 배열은 요소를 하나의 메모리 블록에 저장합니다. 블록이 가득 찬 상태에서 새 요소가 들어오면, 두 배로 큰 블록을 할당하고 기존 요소를 복사한 뒤, 이전 블록을 해제합니다.
initial_capacity의 용량을 가진 빈 배열에서 시작하여 pushes개의 요소를 하나씩 추가합니다. 각 추가 전에 size == capacity이면 재할당을 합니다: 재할당 횟수는 1 증가시키고, 복사된 요소 수에 현재 size를 더한 뒤, capacity를 두 배로 늘립니다.
dynamic_array_growth(pushes, initial_capacity)를 구현하세요.
Input
pushes: 추가할 요소의 개수입니다.
initial_capacity: 빈 배열의 용량입니다.
Output
[reallocations, copied_elements, final_capacity]를 반환하세요.
제약 조건
0 ≤ pushes ≤ 10^7
1 ≤ initial_capacity ≤ 10^6
예시
입력:
pushes = 5
initial_capacity = 1
예상 출력:
expected = [3, 7, 8]입력:
long long pushes = 5;
long long initial_capacity = 1;
예상 출력:
std::vector<long long> expected = {3, 7, 8};입력:
long pushes = 5;
long initial_capacity = 1;
예상 출력:
long[] expected = new long[] {3, 7, 8};설명
용량은 2번째, 3번째, 5번째 요소를 추가할 때 1 → 2 → 4 → 8로 증가하며, 1 + 2 + 4 = 7개의 요소를 복사합니다: [3, 7, 8].
입력:
pushes = 4
initial_capacity = 4
예상 출력:
expected = [0, 0, 4]입력:
long long pushes = 4;
long long initial_capacity = 4;
예상 출력:
std::vector<long long> expected = {0, 0, 4};입력:
long pushes = 4;
long initial_capacity = 4;
예상 출력:
long[] expected = new long[] {0, 0, 4};설명
첫 번째 블록에 네 개의 요소가 모두 들어가므로 재할당이 발생하지 않습니다: [0, 0, 4].
접근 방법
먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.
힌트 1
재할당은 배열이 가득 찼을 때만 일어납니다.
힌트 2
그때마다 현재 원소가 모두 복사되고 용량이 두 배가 됩니다.
힌트 3
push를 하나씩 흉내 내지 않고 두 배가 되는 시점에서 다음 시점으로 건너뛸 수 있습니다.
예상 복잡도
시간 O(log push 횟수), 추가 공간 O(1)
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.