문제 이해하기
서로 다른 숫자들로 구성된 리스트 nums가 주어졌다고 가정해 보겠습니다. 이때 두 가지 종류의 '반전(inversion)'을 정의할 수 있습니다.
- 전역 반전(Global Inversion): 인덱스 i < j를 만족하면서 nums[i] > nums[j]인 경우
- 지역 반전(Local Inversion): 인덱스 i에 대해 nums[i] > nums[i + 1], 즉 바로 인접한 두 원소의 순서가 뒤바뀐 경우
우리가 확인해야 할 것은 전역 반전의 총개수와 지역 반전의 총개수가 서로 같은지 여부입니다.
예를 들어 입력이 nums = [3, 2, 4]라면 결과는 True입니다. 인덱스 0과 1 사이의 반전(3 > 2)은 전역 반전이자 동시에 지역 반전이므로, 두 개수가 일치하기 때문입니다.
핵심 아이디어
모든 지역 반전은 항상 전역 반전에 포함됩니다. 따라서 두 개수가 같으려면, 인접하지 않은 원소 사이에서 발생하는 전역 반전(j ≥ i + 2인 반전)이 하나도 없어야 합니다. 즉, 거리가 2 이상 떨어진 인덱스 쌍 중에서 순서가 뒤바뀐 쌍이 존재하는지만 검사하면 됩니다.
해결 절차
- 리스트의 길이를 l이라고 합니다.
- i를 0부터 l - 3까지 반복합니다.
- j를 i + 2부터 l - 1까지 반복합니다.
- 만약 nums[i] > nums[j]라면 인접하지 않은 전역 반전이 존재하므로 False를 반환합니다.
- 모든 검사를 통과하면 True를 반환합니다.
구현 예제
class Solution:
def solve(self, nums):
l = len(nums)
for i in range(l - 2):
for j in range(i + 2, l):
if nums[i] > nums[j]:
return False
return True
ob = Solution()
nums = [3, 2, 4]
print(ob.solve(nums))
입력
[3, 2, 4]
출력
True
복잡도 분석
이 알고리즘은 두 개의 중첩 반복문을 사용하므로 시간 복잡도는 O(n²)이며, 추가적인 저장 공간을 사용하지 않으므로 공간 복잡도는 O(1)입니다. 참고로 각 원소가 자신의 원래 위치에서 최대 한 칸만 벗어나 있는지를 검사하는 O(n) 방식으로도 동일한 문제를 해결할 수 있습니다.