[LeetCode] #674 Longest Continuous Increasing Subsequence

문제 :

 

문제는 간단하다. 배열이 주어지고, 그 배열에서 "증가하는" subsequence의 길이를 구하는것이다. 첫번째 예시를 보면

[1,3,5,4,7]에서의 증가하는 가장 긴 subsequence는 [1,3,5]이다. 왜냐하면 맨 뒤에 7이 있음에도 불구하고, 그 사이에 5보다 작은 4가 있기에 충족 조건인 "증가하는" subsequence가 될 순 없다.

 

처음에 여러가지 생각을 했다. 어느 자료구조를 써야 효율적으로 풀어낼 수 있을까? 부터 생각했다. 우선, 이 배열은 정렬을 해서는 안 된다. 정렬을 하면 주어진 리스트가 무조건 increasing하는 리스트가 되므로, 정렬을 할 순 없다. 그렇다면, 키 - 값으로 인덱스나 출현 횟수를 저장 할 딕셔너리는 무의미해 보였다. 그래서 일단 단순한 iteration과 조건문으로 구현을 해 보았다. 아래는 내가 제출해 통과한 코드이다.

class Solution:
    def findLengthOfLCIS(self, nums: List[int]) -> int:
        longest = 1
        result = []

        if len(nums) == 1:
            return 1

        for i in range(len(nums) - 1):
            if nums[i] < nums[i+1]:
                longest += 1
            else:
                result.append(longest)
                longest = 1
            result.append(longest)
        
        return max(result)

 

- 먼저, 루프를 돌며 계속 업데이트 될 longest라는 가장 긴 subsquence의 길이를 담을 변수를 선언하고 1로 초기화 했다.

 

- 다음은 result라는 빈 리스트를 선언했다. 이 배열에는 가장 긴 subsequence의 길이를 루프를 돌며 담을것이고, 마지막엔 max(result)를 하여, 이 배열에 담긴 최댓값을 리턴한다. 아래에서 좀 더 자세히 설명 하겠다.

 

- for문을 이용해 nums라는 배열을 순회하며, 현재 인덱스의 다음값이 현재 인덱스보다 크다면(증가하는 subsequence 조건), longest를 업데이트 한다.

 

- 만약 현재 인덱스의 다음값이 현재 인덱스보다 작다면(조건을 벗어나는 케이스), 우리는 현재까지 업데이트된 longest를 결과 배열에 추가 해 주고, longest를 다시 1로 업데이트 해 준다.

 

- 모든 루프를 순회하고 난 뒤, 결과 배열에 더해진 요소들중 최댓값을 리턴한다.

 

위의 [1,3,5,4,7]을 예로 들면 다음과 같다.

 

1. 첫번째 루프 : 1 < 3 이므로, longest는 2로 업데이트 된다.

2. 두번째 루프 : 3 < 5 이므로, longest는 3으로 업데이트 된다.

3. 세번째 루프 : 5 < 4 이므로, if문에서 벗어나 else문으로 진입하여 이전까지 업데이트 된 longest == 3을 result 배열에 추가 해주고, longest를 다시 1로 초기화 해 준다.

4. 네번째 루프: 4 < 7 이므로, if문에서 걸려 longest는 2가 되고, 결과 배열에 2를 추가 해준다.

5. 결과 배열에는 [3,2]의 값들이 담겨있고, 여기서 max를 호출하면 3이 리턴된다.

 

하지만 뭔가 런타임이 길게 나왔다. 뭐 짧게 나오리라곤 생각을 안 했다. 여기서 런타임을 줄일만한 특정한 자료구조나 알고리즘을 사용하지 않았기 때문!

 

----------

 

아래는 GPT가 알려준 런타임이 길게 나온 이유와 그에 대한 해결 방안이다.

현재 주어진 코드는 주어진 리스트에서 가장 긴 연속 증가하는 부분 수열(LCIS)의 길이를 찾는 문제를 해결합니다. 하지만, 이 코드는 비효율적인 부분이 있어서 런타임이 길어질 수 있습니다.

문제점 분석
1. **리스트 추가 연산**: `result.append(longest)`는 매번 리스트에 값을 추가하기 때문에 시간이 걸립니다.
2. **불필요한 리스트 사용**: 최종 결과를 계산하기 위해 리스트 `result`를 사용하지만, 이는 불필요하게 메모리를 사용하고 추가적인 시간이 걸립니다.
3. **최대값 계산**: `max(result)`는 리스트에서 최대값을 찾기 위해 추가적인 O(n) 시간을 소모합니다.

해결 방안
1. **리스트를 사용하지 않고 바로 최대값을 계산**: 리스트 대신 단순히 현재까지의 최대값을 추적하여 메모리 사용과 시간을 절약할 수 있습니다.

개선된 코드
아래는 개선된 코드를 보여줍니다.

class Solution:
    def findLengthOfLCIS(self, nums: List[int]) -> int:
        if not nums:
            return 0

        longest = 1
        current_length = 1

        for i in range(1, len(nums)):
            if nums[i] > nums[i-1]:
                current_length += 1
                longest = max(longest, current_length)
            else:
                current_length = 1

        return longest

 설명
1. **초기화**:
   - `longest`는 가장 긴 연속 증가하는 부분 수열의 길이를 추적합니다.
   - `current_length`는 현재 증가하는 부분 수열의 길이를 추적합니다.
2. **반복문**: 인덱스 `i`를 1부터 시작하여 리스트를 순회합니다.
   - `if nums[i] > nums[i-1]`: 현재 숫자가 이전 숫자보다 크면 `current_length`를 증가시키고, `longest`를 업데이트합니다.
   - `else`: 증가하지 않으면, `current_length`를 1로 리셋합니다.
3. **결과 반환**: 최종적으로 `longest`를 반환합니다.

 최적화 이유
- **리스트 사용 제거**: 불필요한 리스트 사용을 제거하여 메모리 사용을 줄이고, 리스트에 값을 추가하는 시간을 절약합니다.
- **실시간 최대값 갱신**: 최대값을 실시간으로 갱신하여 `max()` 함수의 추가 호출을 피합니다.
- **O(n) 시간 복잡도**: 개선된 코드는 전체 리스트를 한 번만 순회하므로 시간 복잡도는 O(n)입니다.

이 방법을 사용하면 주어진 리스트에서 가장 긴 연속 증가하는 부분 수열의 길이를 효율적으로 찾을 수 있습니다.