Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 풀어보는 키 기반 순열 쿼리 문제

1부터 m 사이의 양의 정수로 이루어진 배열 queries가 주어졌을 때, 다음 규칙에 따라 모든 쿼리 queries[i](i = 0부터 n-1까지, n은 queries의 크기)를 처리해야 합니다.

문제 개요

  • 처음에는 순열 P = [1, 2, 3, ..., m]으로 시작합니다.
  • 현재 인덱스 i에 대해, 순열 P에서 queries[i]의 위치(0부터 시작하는 인덱스)를 찾은 뒤, 해당 값을 P의 맨 앞으로 이동시킵니다.

모든 쿼리를 처리한 후에는, 각 쿼리에서 찾은 위치 값을 담은 배열을 결과로 반환해야 합니다.

예제 살펴보기

예를 들어 queries = [3, 1, 2, 1], m = 5라면 출력은 [2, 1, 2, 1]이 됩니다. 쿼리는 다음과 같은 과정으로 처리됩니다.

  • i = 0: queries[i] = 3, P = [1, 2, 3, 4, 5]. P에서 3의 위치는 2이며, 3을 맨 앞으로 옮기면 P = [3, 1, 2, 4, 5]가 됩니다.
  • i = 1: queries[i] = 1, P = [3, 1, 2, 4, 5]. P에서 1의 위치는 1이며, 1을 맨 앞으로 옮기면 P = [1, 3, 2, 4, 5]가 됩니다.
  • i = 2: queries[i] = 2, P = [1, 3, 2, 4, 5]. P에서 2의 위치는 2이며, 2를 맨 앞으로 옮기면 P = [2, 1, 3, 4, 5]가 됩니다.
  • i = 3: queries[i] = 1, P = [2, 1, 3, 4, 5]. P에서 1의 위치는 1이며, 1을 맨 앞으로 옮기면 P = [1, 2, 3, 4, 5]가 됩니다.
  • 최종적으로 결과 배열은 [2, 1, 2, 1]입니다.

해결 접근 방법

이 문제는 단순 시뮬레이션 방식으로 해결할 수 있습니다. 각 쿼리마다 순열에서 목표 값의 위치를 찾아 기록하고, 그 값을 맨 앞으로 옮긴 새로운 순열을 만들면 됩니다. 구체적인 단계는 다음과 같습니다.

  1. 결과를 저장할 배열 ret과 순열을 저장할 배열 v를 선언합니다.
  2. v에 1부터 m까지의 값을 차례대로 삽입하여 초기 순열을 구성합니다.
  3. queries의 각 값 x에 대해 아래 작업을 반복합니다.
    • pos := -1로 초기화하고, 임시 배열 temp를 선언합니다.
    • v를 순회하면서 v[i] == x를 만족하는 첫 번째 위치 pos를 찾습니다.
    • temp의 맨 앞에 v[pos]를 삽입합니다.
    • pos 위치를 제외한 나머지 원소들을 순서대로 temp 뒤에 추가합니다.
    • v := temp로 갱신한 뒤, ret에 pos를 추가합니다.
  4. 모든 쿼리 처리가 끝나면 ret을 반환합니다.

이 알고리즘의 시간 복잡도는 각 쿼리마다 순열 전체를 탐색하므로 O(n × m)이며, 공간 복잡도는 O(m)입니다.

C++ 구현 코드

다음 구현을 통해 동작 방식을 더 잘 이해할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<int> v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
        cout << v[i] << ", ";
    }
    cout << "]"<<endl;
}
class Solution {
public:
    vector<int> processQueries(vector<int>& q, int m) {
        vector<int> ret;
        vector<int> v;
        for (int i = 0; i < m; i++)
            v.push_back(i + 1);
        for (int x : q) {
            int pos = -1;
            vector<int> temp;
            for (int i = 0; i < v.size(); i++) {
                if (v[i] == x) {
                    pos = i;
                    break;
                }
            }
            temp.insert(temp.begin(), v[pos]);
            for (int i = 0; i < v.size(); i++) {
                if (i == pos)
                    continue;
                temp.push_back(v[i]);
            }
            v = temp;
            ret.push_back(pos);
        }
        return ret;
    }
};
main(){
    Solution ob;
    vector<int> v = {3,1,2,1};
    print_vector(ob.processQueries(v, 5));
}

실행 결과 확인

입력

{3,1,2,1}, 5

출력

[2, 1, 2, 1]