파이썬으로 특수 배열에서 X 찾기 — X 이상인 요소가 정확히 X개인 값 구하기

문제 개요

모든 요소가 0 또는 양수로만 이루어진 배열 nums가 있다고 가정해 봅시다. 만약 어떤 수 x에 대해 배열 안에 x보다 크거나 같은 요소가 정확히 x개 존재한다면, 이 배열을 '특수 배열(special array)'이라고 부릅니다. 여기서 중요한 점은 x가 반드시 배열의 요소일 필요는 없다는 것입니다.

배열이 특수 배열이라면 조건을 만족하는 x를 찾아 반환하고, 그런 값이 존재하지 않는다면 -1을 반환하면 됩니다.

예시

예를 들어 입력이 nums = [4, 6, 7, 7, 1, 0]이라면 결과는 4입니다. 배열에서 4보다 크거나 같은 숫자는 4, 6, 7, 7로 정확히 4개이기 때문입니다.

풀이 접근 방법

가장 직관적인 방법은 가능한 모든 후보 값 x(0부터 배열의 최댓값까지)를 하나씩 확인하는 완전 탐색입니다. 단계별로 살펴보면 다음과 같습니다.

• 0부터 nums의 최댓값까지 각 후보 값 i에 대해 반복합니다.
• 배열을 순회하면서 i보다 크거나 같은 요소의 개수(count)를 셉니다.
• count와 i가 같다면 그 값이 정답이므로 i를 반환합니다.
• 모든 후보를 확인한 후에도 조건을 만족하는 값이 없다면 -1을 반환합니다.

파이썬 구현 예제

다음 코드를 통해 위 접근 방식을 더 잘 이해할 수 있습니다.

def solve(nums):
    for i in range(max(nums) + 1):
        count = 0
        for j in nums:
            if j >= i:
                count += 1
        if count == i:
            return i
    return -1

nums = [4, 6, 7, 7, 1, 0]
print(solve(nums))

주의할 점은 return -1이 반드시 바깥쪽 for 루프가 끝난 후에 실행되어야 한다는 것입니다. 루프 내부에 들어가면 첫 번째 후보 값 검사 직후 프로그램이 종료되어 올바른 답을 구할 수 없습니다.

입력

[4, 6, 7, 7, 1, 0]

출력

4

복잡도 분석

이 풀이는 외부 루프가 최대 max(nums) + 1번, 내부 루프가 배열 길이 n번 실행되므로 시간 복잡도는 O(n × m)입니다(여기서 m은 배열의 최댓값). 추가적인 자료구조를 사용하지 않으므로 공간 복잡도는 O(1)입니다.

참고로 이 문제는 카운팅 기법을 활용하면 더 효율적으로 해결할 수 있습니다. 각 값의 등장 횟수를 세어 누적합을 미리 계산해 두면, 임의의 x에 대해 'x 이상인 요소의 개수'를 상수 시간에 구할 수 있어 전체 시간 복잡도를 O(n + m)까지 줄일 수 있습니다.