Python으로 정렬된 배열에서 부분 집합의 합으로 표현할 수 없는 가장 작은 양의 정수 찾기

문제 개요

오름차순으로 정렬된 양의 정수 배열이 주어졌을 때, 이 배열의 어떤 부분 집합의 합으로도 표현할 수 없는 가장 작은 양의 정수를 찾아야 합니다. 단, 시간 복잡도 O(n) 안에 문제를 해결해야 한다는 조건이 있습니다.

예를 들어 입력이 A = [1, 4, 8, 12, 13, 17]이라면 출력은 2가 됩니다. 배열에 1은 존재하지만, 2를 만들 방법이 없기 때문입니다(1 다음 요소가 4이므로 1+4=5만 가능).

해결 아이디어

핵심 원리는 다음과 같습니다. 현재까지 만들 수 있는 합의 범위가 [1, answer − 1]이라고 가정할 때, 다음 요소 A[i]가 answer보다 작거나 같으면 A[i]를 더해 만들 수 있는 범위를 [1, answer + A[i] − 1]로 확장할 수 있습니다. 반면 A[i]가 answer보다 크다면 answer라는 값 자체를 절대 만들 수 없으므로, 그 순간의 answer가 곧 정답이 됩니다.

알고리즘 단계

1. n := 배열 A의 크기로 설정
2. answer := 1로 초기화
3. i를 0부터 n−1까지 순회하며 다음을 반복:
   • A[i] ≤ answer이면 answer := answer + A[i]
   • 그렇지 않으면 루프를 종료
4. answer 값을 반환

Python 구현 예제

def get_smallest_element(A):
    n = len(A)
    answer = 1
    for i in range(0, n):
        if A[i] <= answer:
            answer = answer + A[i]
        else:
            break
    return answer

A = [1, 4, 8, 12, 13, 17]
print(get_smallest_element(A))

입력

[1, 4, 8, 12, 13, 17]

출력

2

동작 과정 추적

예제 배열 [1, 4, 8, 12, 13, 17]에 대해 알고리즘이 어떻게 진행되는지 살펴보겠습니다.

• 초기 상태: answer = 1
• A[0] = 1 ≤ 1 → answer = 1 + 1 = 2 (이제 [1, 1] 범위를 만들 수 있음)
• A[1] = 4 > 2 → 루프 종료
• 최종 결과: 2

answer가 2일 때 배열의 첫 번째 요소가 이미 4이므로, 2와 3은 어떤 부분 집합의 합으로도 만들 수 없습니다. 따라서 2가 정답이 됩니다.

복잡도 분석

• 시간 복잡도: O(n) — 배열을 한 번만 순회하면 됩니다.
• 공간 복잡도: O(1) — 추가 메모리를 거의 사용하지 않습니다.