문제 소개
정수 배열이 주어졌을 때, 한 번의 연산에서 n-1개의 요소를 선택해 각각 1씩 증가시킬 수 있습니다. 목표는 이러한 연산을 반복하여 배열의 모든 요소를 동일하게 만드는 데 필요한 총 연산 횟수를 계산하는 것입니다.
예를 들어 [1, 2, 3]이라는 배열이 있다면, 모든 요소를 같게 만들기 위해 총 3번의 연산이 필요합니다. 가장 직관적인 해결 방법은 매 단계마다 배열에서 가장 큰 값을 찾고, 나머지 요소들을 1씩 증가시키는 것입니다. 이를 코드로 작성해 보겠습니다.
방법 1: 시뮬레이션 방식
def main():
# 배열 초기화
arr = [1, 2, 3]
# 연산 횟수를 0으로 초기화
no_of_operations = 0
flag = 0
# 모든 요소가 같아질 때까지 연산 수행
while not are_equal(arr):
flag = 1
# 리스트에서 최댓값 찾기
maximum = max(arr)
# 최댓값을 제외한 나머지 요소 1씩 증가
for i in range(len(arr)):
if arr[i] != maximum:
arr[i] += 1
# 연산 횟수 1 증가
no_of_operations += 1
print(no_of_operations) if flag == 0 else print(no_of_operations + 1)
# 모든 요소가 동일한지 확인하는 함수
def are_equal(arr):
global no_of_operations
for i in range(len(arr) - 1):
if arr[i] != arr[i + 1]:
return False
return True
if __name__ == '__main__':
main()
실행 결과
3
위 프로그램을 실행하면 다음과 같이 3이 출력됩니다.
하지만 이 방법은 배열의 길이가 길거나 요소 간 차이가 클수록 반복 횟수가 많아져 계산 시간이 오래 걸린다는 단점이 있습니다.
방법 2: 수학적 접근 (합과 최솟값 활용)
n-1개의 요소를 1씩 증가시키는 것은 상대적인 관점에서 보면 나머지 하나의 요소를 1씩 감소시키는 것과 같습니다. 따라서 '모든 요소를 최솟값까지 낮추는' 문제로 치환할 수 있으며, 연산 횟수는 다음 공식으로 한 번에 구할 수 있습니다.
연산 횟수 = 배열의 합 − (배열 길이 × 최솟값)
- 배열 요소들의 합(sum)을 구합니다.
- 배열에서 가장 작은 값(min)을 찾습니다.
sum − (length × smallest)공식에 대입한 결과를 출력합니다.
예제 코드
# 배열 초기화
arr = [1, 2, 3]
# 배열의 길이
length = len(arr)
# 배열 요소들의 합
elements_sum = sum(arr)
# 모든 요소 중 최솟값
smallest = min(arr)
# 연산 횟수 계산 후 출력
print(elements_sum - (length * smallest))
실행 결과
3
위 코드를 실행하면 첫 번째 방법과 동일하게 3이 출력되지만, 반복문 없이 한 번의 계산으로 답을 얻을 수 있습니다.
결론
두 번째 방법은 첫 번째 방법에 비해 구현이 훨씬 간단하고, O(n) 시간 복잡도로 답을 구할 수 있어 대규모 배열에서도 빠르게 동작합니다. 실무에서도 이처럼 문제를 수식으로 단순화하면 성능을 크게 개선할 수 있습니다. 튜토리얼 내용 중 궁금한 점이 있다면 댓글로 남겨주세요!