파이썬(Python)으로 k 이상인 요소가 정확히 k개인 값 k 찾는 프로그램

문제 개요

음수가 아닌 숫자로만 구성된 리스트 nums가 주어졌다고 가정해 보겠습니다. 이때 nums 안에서 k보다 크거나 같은 요소가 정확히 k개 존재하는 값 k를 찾아야 합니다. 만약 그러한 값을 찾을 수 없다면 -1을 반환합니다.

예를 들어 입력이 nums = [6, 4, 0, 8, 2, 9]라면 출력은 4입니다. 왜냐하면 4보다 크거나 같은 요소가 정확히 4개, 즉 [6, 4, 8, 9]가 존재하기 때문입니다.

해결 접근 방법

이 문제는 내림차순 정렬과 인덱스 비교를 활용하면 효율적으로 해결할 수 있습니다. 해결 과정은 다음과 같습니다.

• 리스트 nums를 내림차순으로 정렬합니다.

• i를 1부터 len(nums) - 1까지 반복하며 다음 조건을 검사합니다.

  • i > nums[i - 1]이면 반복문을 종료합니다.

  • 그렇지 않고 i > nums[i]이면 i를 반환합니다.

• 조건을 만족하는 값이 없으면 -1을 반환합니다.

예제 코드

더 나은 이해를 위해 다음 파이썬 구현 예제를 살펴보겠습니다.

def solve(nums):
    nums.sort(reverse=True)
    for i in range(1, len(nums)):
        if i > nums[i - 1]:
            break
        elif i > nums[i]:
            return i
    return -1

nums = [6, 4, 0, 8, 2, 9]
print(solve(nums))

입력

[6, 4, 0, 8, 2, 9]

출력

4

동작 원리

내림차순으로 정렬된 [9, 8, 6, 4, 2, 0]에서 인덱스 i와 해당 위치의 값을 비교하는 방식으로 알고리즘이 동작합니다. 정렬된 상태에서 인덱스 i 위치의 값이 i보다 작다는 것은, 그 지점부터 끝까지 남은 요소의 개수가 정확히 i개이면서 모두 i 이상이라는 의미이므로 조건을 만족하는 k를 찾은 것입니다. 이 문제는 논문 인용 지표로 널리 알려진 'H-지수(H-Index)' 계산과 유사한 패턴을 가진 대표적인 정렬 기반 알고리즘 문제입니다.