이 문제에서는 크기가 N인 배열 arr[]와 정수 M이 주어집니다. 우리의 목표는 배열에서 마지막으로 제거되는 요소의 위치를 찾는 것입니다.
요소 제거 규칙
배열에서 값을 제거하는 작업은 다음 규칙에 따라 진행됩니다.
- 배열의 요소 arr[i]를 확인했을 때, arr[i] > M이라면 해당 값을 제거하고 arr[i] − M을 계산하여 배열의 맨 뒤에 추가합니다.
- 만약 arr[i] ≤ M이라면, 해당 값은 새로 추가되지 않고 그대로 제거됩니다.
위 작업은 배열이 완전히 빌 때까지 반복해서 수행합니다.
예제로 문제 이해하기
입력
arr[] = {5, 4, 8}, M = 3출력
3
설명
규칙에 따라 값을 제거하는 과정은 다음과 같습니다.
{5, 4, 8} -> {4, 8, 2} -> {8, 1, 2} -> {1, 2, 5} -> {2, 5} -> {5} -> {2} ->
빈 배열.
마지막으로 제거된 값은 8이며, 원래 배열에서의 위치는 3입니다.
해결 접근 방법
이 문제의 핵심 아이디어는 마지막으로 제거되는 값은 항상 ceil(arr[i] / M)이 가장 큰 요소라는 사실입니다. 여기서 ceil은 올림 연산을 의미하며, 각 요소가 배열에서 완전히 사라지기 위해 필요한 총 제거 횟수를 나타냅니다.
즉, ceil(arr[i] / M) 값이 클수록 해당 요소는 더 많은 순환을 거쳐야 하므로 늦게 제거됩니다. 참고로 이 값이 서로 같은 요소가 여러 개라면, 배열에서 더 뒤쪽(인덱스가 큰)에 있는 요소가 마지막에 제거됩니다.
따라서 배열을 한 번 순회하면서 ceil(arr[i] / M) 값이 최대인 요소의 위치를 저장해 두면, 그 위치가 곧 마지막으로 제거되는 요소의 위치가 됩니다. 코드에서는 정수 나눗셈과 나머지 연산을 조합하여 별도의 실수 연산 없이 올림 값을 계산합니다.
C++ 구현 예제
아래 프로그램은 위 접근 방식이 실제로 동작하는 모습을 보여줍니다.
#include <iostream>
using namespace std;
int findLastRemPos(int arr[], int n, int m){
for (int i = 0; i < n; i++) {
arr[i] = (arr[i] / m + (arr[i] % m != 0));
}
int lastRemPos = -1, largestVal = -1;
for (int i = n - 1; i >= 0; i--) {
if (largestVal < arr[i]) {
largestVal = arr[i];
lastRemPos = i;
}
}
return lastRemPos + 1;
}
int main(){
int arr[] = {5, 4, 8, 1};
int n = sizeof(arr) / sizeof(arr[0]);
int m = 3;
cout<<"The position of last removed element in the array is "<<findLastRemPos(arr, n, m);
return 0;
}
실행 결과
The position of last removed element in the array is 3
복잡도 분석
- 시간 복잡도: O(N) — 배열을 최대 두 번 순회합니다.
- 공간 복잡도: O(1) — 별도의 자료 구조 없이 상수 공간만 사용합니다.