목차

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

---

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

• 문제 링크

• 내 풀이

• 문제 요약
  • 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

←이전 글: 4월 5주차 알고리즘 문제 다음 글: Introduction to Shortest Path algorithm → 카테고리로 돌아가기 ↩