← 전체 글로 돌아가기
competitive-programming2021년 3월 1일1분 분량

[Codeforces] 1490D. Permutation Transformation 풀이

수정일: 2021년 9월 11일

Divide and conquer
지원 언어:enko

#Problem

1490D. Permutation Transformation

#Approach

여기서 실제 이진 트리를 구성할 필요는 전혀 없습니다.
아래는 _divide and conquer_에 기반한 풀이입니다.

depth←[0,0,…0]depth \leftarrow [0, 0, … 0]
헬퍼 함수 findDepth(left, right, currentDepth)에서,

  1. [left,right][left, right] 구간의 최댓값을 찾고, depth 값 depth[mid]를 currentDepth로 갱신합니다.
  2. findDepth(left, mid-1, currentDepth+1)을 재귀적으로 호출합니다.
  3. findDepth(mid+1, right, currentDepth+1)을 재귀적으로 호출합니다.

main 함수에서는 단순히 헬퍼 함수 findDepth(0, n-1, 0)을 호출하고 depth 배열을 출력합니다.

#Code

#cpp

/**
 * author: jooncco
 * written: 2021. 3. 1. Mon. 17:58:38 [UTC+9]
 **/

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
#include <deque>
#include <queue>
#include <set>
#include <cmath>
using namespace std;

#define FAST_IO ios_base::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef deque<int> di;
typedef deque<ii> dii;

int t,n,arr[110],d[110];

void dfs(int l, int r, int cur) {

    int mx= 0, mxIdx;
    for (int i=l; i <= r; ++i) {
        if (mx < arr[i]) {
            mx= arr[i];
            mxIdx= i;
        }
    }
    d[mxIdx]= cur;

    if (mxIdx > l) dfs(l,mxIdx-1,cur+1);
    if (mxIdx < r) dfs(mxIdx+1,r,cur+1);
}

int main() {

    FAST_IO;
    cin >> t;
    while (t--) {
        cin >> n;
        for (int i=0; i < n; ++i) cin >> arr[i];
        dfs(0,n-1,0);
        for (int i=0; i < n; ++i) {
            if (i) cout << " ";
            cout << d[i];
        }
        cout << '\n';
    }
}

#java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private final static FastScanner sc= new FastScanner();
    private static int t,n;

    public static void main(String[] args) {
        t= sc.nextInt();
        while (t-- > 0) {
            n= sc.nextInt();
            int arr[]= new int[n];
            for (int i=0; i < n; ++i) {
                arr[i]= sc.nextInt();
            }
            int ans[]= new int[n];
            findDepth(arr, ans, 0, n-1, 0);
            StringBuilder sb= new StringBuilder();
            for (int i=0; i < n; ++i) {
                if (i > 0) sb.append(" ");
                sb.append(ans[i]);
            }
            System.out.println(sb);
        }
    }

    private static void findDepth(final int[] arr, int[] depth, int l, int r, int d) {
        if (r < 0 || l >= n) return;
        if (l == r) {
            depth[l]= d;
            return;
        }
        int maxVal= 0, idx= -1;
        for (int i=l; i <= r; ++i) {
            if (arr[i] > maxVal) {
                idx= i;
                maxVal= arr[i];
            }
        }
        depth[idx]= d;
        if (l < idx) findDepth(arr, depth, l, idx-1, d+1);
        if (r > idx) findDepth(arr, depth, idx+1, r, d+1);
    }
}

class FastScanner {
    BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st= new StringTokenizer("");
    String next() {
        while (!st.hasMoreTokens()) {
            try {
                st= new StringTokenizer(br.readLine());
            } catch (IOException ex) {}
        }
        return st.nextToken();
    }

    int nextInt() {
        return Integer.parseInt(next());
    }
    long nextLong() {
        return Long.parseLong(next());
    }
}

#Complexity

  • Time: O(n2)O(n^2)
  • Space: O(n)O(n)