숫자 k와 열려 있는 앱의 ID를 저장하는 n개의 정수 요소를 담은 배열 arr[n]이 주어졌을 때, k개의 최근 사용 앱을 표시하는 것이 이번 문제의 목표입니다. 마치 Alt+Tab 키를 눌렀을 때 최근 앱 목록이 표시되고, 가장 최근에 사용한 앱이 맨 앞에 오듯이 배열을 재구성해야 합니다. 각 ID의 위치는 시스템 내 서로 다른 앱을 의미합니다.
배열 위치의 의미
- arr[0]의 ID는 현재 사용 중인 앱의 ID입니다.
- arr[1]의 ID는 가장 최근에 사용된 앱의 ID입니다.
- arr[n-1]의 ID는 가장 오래전에 사용된 앱의 ID입니다.
참고: Alt+Tab 키를 누르면 인덱스 0(현재 사용 중인 앱)부터 시작하여 열려 있는 모든 앱을 순회하는 포인터가 작동한다고 생각하면 이해하기 쉽습니다.
예제
입력: arr[] = {1, 2, 3, 4, 5}, k=2
출력: 3 1 2 4 5
설명: ID가 3인 앱으로 전환하려는 경우, 해당 앱이 현재 활성 앱이 되고
나머지 앱들은 최근 사용 순서대로 재배열됩니다.
입력: arr[] = {6, 1, 9, 5, 3}, k=3
출력: 5 6 1 9 3접근 방식
- 배열 arr[n]과 값 k를 입력으로 받습니다.
- 사용자가 전환하려는 앱의 인덱스 k를 확인합니다.
- 인덱스 k에 있는 ID를 현재 활성 앱으로 지정하고, 나머지 앱들을 최근 사용 순서에 맞게 재배열합니다.
- 결과를 출력합니다.
알고리즘
시작
1단계 -> 최근 사용 앱 순서로 배열을 갱신하는 함수 선언
void recently(int* arr, int size, int elem)
int index = 0 선언
index = (elem % size) 설정
int temp = index, id = arr[index] 선언 및 초기화
temp > 0 인 동안 반복
arr[temp] = arr[--temp] 실행
반복 종료
arr[0] = id 설정
2단계 -> 배열 요소를 출력하는 함수 선언
void print(int* arr, int size)
i = 0 부터 i < size 까지 반복
arr[i] 출력
반복 종료
3단계 -> main() 함수에서
int elem = 3 으로 설정
배열 int arr[] = { 6, 1, 9, 5, 3 } 선언
크기 계산: int size = sizeof(arr) / sizeof(arr[0])
recently(arr, size, elem) 호출
print(arr, size) 호출
종료C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
// 배열을 최근 사용(MRU) 순서로 갱신하는 함수
void recently(int* arr, int size, int elem) {
int index = 0;
index = (elem % size);
int temp = index, id = arr[index];
while (temp > 0) {
arr[temp] = arr[--temp];
}
arr[0] = id;
}
// 배열 요소 출력 함수
void print(int* arr, int size) {
for (int i = 0; i < size; i++)
cout << arr[i] << " ";
}
int main() {
int elem = 3;
int arr[] = { 6, 1, 9, 5, 3 };
int size = sizeof(arr) / sizeof(arr[0]);
recently(arr, size, elem);
cout<<"array in most recently used fashion : ";
print(arr, size);
return 0;
}실행 결과
array in most recently used fashion : 5 6 1 9 3
이 알고리즘의 시간 복잡도는 O(k)이며, 여기서 k는 선택된 앱의 인덱스입니다. 대상 앱을 맨 앞으로 이동시키기 위해 해당 인덱스까지의 요소들을 한 칸씩 뒤로 밀어내기 때문입니다. 공간 복잡도는 추가 메모리를 사용하지 않으므로 O(1)로 매우 효율적입니다. 이러한 MRU 방식은 실제 운영체제의 앱 전환 기능이나 캐시 관리 시스템에서도 널리 활용되는 개념입니다.