5월 1주차 알고리즘 문제 - 두 수가 교차하는 경우의 수를 다루는 방법

목차

두 수가 교차하는 경우의 수를 다루는 방법

두 수가 교차하는 경우의 수를 다루는 방법

문제 링크
내 풀이
문제 요약
- Semi-Ordered Permutation이란, 처음이 가장 작은 수이고 가장 마지막이 가장 큰 수이며, 중간에는 어떤 수든 나타날 수 있는 순열이다.
- 순열이 주어졌을때 인접한 두 수를 swap하여 Semi-Ordered Permutation을 만드는 최소 교환 횟수를 구하라.
풀이 요약
- 가장 작은 수가 1에 도착하는 횟수 + 가장 큰 수가 n에 도착하는 횟수를 구하면 된다.
- 이 때 두 수가 교차하는 경우 1을 빼주면 된다.

def semiOrderedPermutation(self, A: List[int]) -> int:
    n = len(A)
    i, j = A.index(1), A.index(n)
    return i + n - 1 - j - (i > j)

2024-05-05