파이썬으로 배열이 '아름다운' 배열인지 판별하는 방법

문제 소개

중복 없는 고유한 원소들로 구성된 배열 nums가 주어졌을 때, 이 배열이 다음 두 조건을 모두 만족하는지 확인하는 문제입니다.

1. 범위 조건: 모든 원소가 1부터 n(배열의 길이) 사이의 값이어야 합니다.
2. 정렬 조건: 배열이 오름차순으로 정렬되어 있으면 안 됩니다.

예를 들어 입력이 nums = [2,6,1,5,3,4]라면 두 조건을 모두 충족하므로 결과는 True가 됩니다.

풀이 접근 방식

이 문제는 배열을 한 번만 순회하면 되므로 O(n) 시간 복잡도로 해결할 수 있습니다. 단계별로 살펴보면 다음과 같습니다.

• n ← 배열 nums의 길이
• total ← nums[0] (원소의 합을 누적하는 변수)
• is_sorted ← True (오름차순 정렬 여부를 나타내는 플래그)
• i를 1부터 n-1까지 반복하면서:
  • nums[i]와 nums[i-1]이 같으면 False 반환 (중복 원소 존재)
  • nums[i]가 nums[i-1]보다 작으면 is_sorted를 False로 변경
  • total에 nums[i]를 더함
• 반복이 끝난 후에도 is_sorted가 True라면 False 반환 (배열이 오름차순으로 정렬된 경우)
• 마지막으로 total이 1부터 n까지 자연수의 합, 즉 n×(n+1)/2와 같은지 비교하여 같으면 True, 다르면 False 반환

핵심 아이디어는 등차수열의 합 공식입니다. 원소들이 중복 없이 1부터 n 사이에 존재한다면 전체 합은 반드시 n×(n+1)/2와 일치해야 하므로, 이 값 하나만 비교해도 범위 조건을 손쉽게 검증할 수 있습니다.

구현 코드

def solve(nums):
    n = len(nums)

    total = nums[0]
    is_sorted = True

    for i in range(1, n):
        if nums[i] == nums[i - 1]:
            return False

        if nums[i] < nums[i - 1]:
            is_sorted = False
        total += nums[i]

    if is_sorted:
        return False

    return total == (n * (n + 1) // 2)

nums = [2,6,1,5,3,4]
print(solve(nums))

실행 결과

입력:

[2,6,1,5,3,4]

출력:

True

정리

이 풀이는 단 한 번의 순회만으로 중복 여부, 정렬 여부, 원소 범위 세 가지를 모두 검사합니다. 시간 복잡도는 O(n), 공간 복잡도는 O(1)로 매우 효율적이며, 등차수열 합 공식을 활용해 별도의 추가 배열 없이 범위 조건까지 확인할 수 있다는 점이 가장 큰 특징입니다.