본문 바로가기
Python/알고리즘

[COS PRO 1급 #2-5] 언제까지 오르막길이야

by 포푸리 (POPOOLY) 2023. 2. 19.
반응형

문제설명

자연수가 들어있는 리스트가 있습니다. 이 리스트에서, 숫자가 연속해서 증가하는 가장 긴 구간의 길이를 구하려 합니다. 단, 바로 전 숫자와 현재 숫자가 같은 경우는 증가한 것으로 보지 않습니다.

예를 들어 리스트에 순서대로 [3, 1, 2, 4, 5, 1, 2, 2, 3, 4]가 들어있는 경우, [1, 2, 4, 5]가 들어있는 구간이 숫자가 연속해서 증가한 가장 긴 구간이며, 길이는 4입니다.

자연수가 들어있는 리스트 arr가 매개변수로 주어질 때, 숫자가 연속해서 증가하는 가장 긴 구간의 길이를 return 하도록 solution 함수를 완성해주세요.

매개변수 설명

자연수가 들어있는 리스트 arr가 solution 함수의 매개변수로 주어집니다.
* arr의 길이는 2 이상 200,000 이하입니다.
* arr의 원소는 1 이상 1,000,000 이하의 자연수입니다.

return 값 설명

숫자가 연속해서 증가하는 가장 긴 구간의 길이를 return 해주세요.
* 길이가 2 이상인 증가하는 구간이 없다면 1을 return 해주세요.

예시

| arr                            | return |
|--------------------------------|--------|
| [3, 1, 2, 4, 5, 1, 2, 2, 3, 4] | 4      |

예시 설명

숫자 [1, 2, 4, 5]가 들어있는 구간이 숫자가 연속해서 증가하는 가장 긴 구간이며, 길이는 4입니다.

현재 숫자가 바로 이전 숫자와 같은 경우에는 증가했다고 보지 않습니다. [1, 2, 2, 3, 4]가 들어있는 구간은 [2, 2]가 연속해서 증가한 부분이 아니므로, [1, 2]가 들어있는 구간과 [2, 3, 4]가 들어있는 구간으로 나누어야 합니다.

문제 코드

def solution(arr):
    #여기에 코드를 작성해주세요.
    answer = 0
    return answer

풀이 1

def solution(arr):
    answer = 1
    temp = 1
    
    for i in range(1, len(arr));
    	# temp는 숫자가 연속해서 증가하는 길이
    	if arr[i] > arr[i-1]:
        	temp += 1
        # temp가 answer보다 크면 temp가 i까지 중 숫자가 연속해서 증가하는 가장 긴 구간
        elif temp > answer:
        	answer = temp
            temp = 1
    return answer

풀이 2

def solution(arr):
    dp = [1 for _ in range(len(arr))]
    for i in range(1, len(arr)):
    	# dp[i]는 i까지 연속해서 증가한 구간의 길이
        if arr[i] > arr[i-1]:
            dp[i] = dp[i-1] + 1
    answer = max(dp)
    return answer

댓글