문제 설명
배열 arr가 주어졌다고 가정해 봅시다. 우리는 arr에 몇 가지 연산을 수행하여 아래 조건들을 만족하도록 만들어야 합니다.
- arr의 첫 번째 요소는 반드시 1이어야 합니다.
- 인접한 두 요소 간의 절댓값 차이는 최대 1 이하여야 합니다.
이를 위해 사용할 수 있는 두 가지 연산이 있으며, 각 연산은 원하는 만큼 여러 번 수행할 수 있습니다.
- arr의 임의의 값을 더 작은 양수로 감소시킵니다.
- arr의 요소들을 임의의 순서로 재배열합니다.
목표는 위 조건들을 만족하도록 연산을 수행한 뒤, 배열에서 가능한 최댓값을 구하는 것입니다.
예시
입력이 arr = [3,3,2,3,2]라고 해봅시다. 이 경우 출력은 3이 됩니다. 마지막 요소를 1로 감소시킨 뒤 배열을 [1,2,3,3,3]과 같이 재배열하면 모든 조건을 만족하며, 이때 최댓값은 3입니다.
해결 방법 (그리디 접근)
이 문제는 그리디(Greedy) 방식으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
배열을 오름차순으로 정렬하면, 각 위치에서 이전 요소보다 최대 1만큼 큰 값을 유지하는 것이 최선입니다.
첫 번째 요소는 조건에 따라 반드시 1로 설정합니다.
이후 각 요소를 순회하면서, 해당 요소를 '이전 요소 + 1'과 자기 자신 중 더 작은 값으로 만듭니다. 이렇게 하면 인접 요소 간 차이가 1 이하라는 조건이 보장되고, 각 위치에서 가능한 한 큰 값을 유지할 수 있습니다.
따라서 해결 단계는 다음과 같습니다.
- 리스트 arr를 정렬합니다.
- arr[0] := 1 로 설정합니다.
- i를 1부터 (arr의 길이 − 1)까지 순회하며 다음을 수행합니다.
- arr[i] := min(arr[i − 1] + 1, arr[i])
- arr의 최댓값을 반환합니다.
구현 예제
다음 파이썬 코드를 통해 더 잘 이해할 수 있습니다.
def solve(arr):
arr.sort()
arr[0] = 1
for i in range(1, len(arr)):
arr[i] = min(arr[i - 1] + 1, arr[i])
return max(arr)
arr = [3,3,2,3,2]
print(solve(arr))
입력
[3,3,2,3,2]
출력
3
복잡도 분석
정렬에 O(n log n)의 시간이 소요되고, 이후 선형 순회에 O(n)이 걸리므로 전체 시간 복잡도는 O(n log n)입니다. 추가 공간은 제자리 정렬 기준 O(1)입니다.