리트코드 - 1732. Find the Highest Altitude

https://leetcode.com/problems/find-the-highest-altitude/description/?envType=study-plan-v2&envId=leetcode-75

Find the Highest Altitude - LeetCode

gain 리스트를 순회하면서 연산을 수행하고, 최댓값을 갱신해주기만 하면 쉽게 풀 수 있다.

 

class Solution:
    def largestAltitude(self, gain: List[int]) -> int:
        now = 0  # O(1)
        highest = 0  # O(1)
        for altitude in gain:  # gain 리스트의 길이를 n이라고 할 때, O(n)
            now += altitude  # O(1), 매우 큰 수의 연산일 경우 O(n)
            highest = max(now, highest)  # O(1) 매우 큰 수의 연산일 경우 O(n)

        return highest  # O(1)

 

숫자 간의 연산에서 숫자의 크기가 매우 클 경우, 일반적으로 간주되는 O(1) 시간 복잡도가 적용되지 않을 수 있다. 이는 특히 큰 수를 다루는 경우에 해당한다.

일반적인 프로그래밍 언어에서 기본 데이터 타입(예: int, long 등)을 사용하는 정수 연산은 CPU에서 직접 지원되므로 일반적으로 O(1)의 시간 복잡도를 갖는다. 그러나 숫자의 크기가 표준 데이터 타입의 범위를 넘어서는 경우(예를 들어, 수백 자리 혹은 그 이상의 큰 정수), 다음과 같은 상황이 발생할 수 있다:

1. 숫자를 저장하는데 더 많은 공간 필요: 큰 수는 여러 개의 데이터 단위(바이트, 워드)에 걸쳐 저장된다.
2. 연산에 더 많은 시간 소요: 큰 수의 각 자릿수에 대한 연산이 필요하며, 이는 전체 숫자 길이에 비례하는 시간이 소요된다. 예를 들어, 두 개의 큰 수를 더하는 데 필요한 시간은 숫자의 자릿수에 비례하여 O(n)이 된다.

따라서, 매우 큰 수를 다루는 상황에서는 연산의 시간 복잡도를 O(1)이 아닌 O(n)으로 고려해야 한다.