백준 2491. 수열 (파이썬)

 

 

문제 2491번
0에서부터 9까지의 숫자로 이루어진 N개의 숫자가 나열된 수열이 있다. 그 수열 안에서 연속해서 커지거나(같은 것 포함), 혹은 연속해서 작아지는(같은 것 포함) 수열 중 가장 길이가 긴 것을 찾아내어 그 길이를 출력하는 프로그램을 작성하라. 
예를 들어 수열 1, 2, 2, 4, 4, 5, 7, 7, 2 의 경우에는 1 ≤ 2 ≤ 2 ≤ 4 ≤ 4 ≤ 5 ≤ 7 ≤ 7 이 가장 긴 구간이 되므로 그 길이 8을 출력한다. 수열 4, 1, 3, 3, 2, 2, 9, 2, 3 의 경우에는 3 ≥ 3 ≥ 2 ≥ 2 가 가장 긴 구간이 되므로 그 길이 4를 출력한다. 또 1, 5, 3, 6, 4, 7, 1, 3, 2, 9, 5 의 경우에는 연속해서 커지거나 작아지는 수열의 길이가 3 이상인 경우가 없으므로 2를 출력하여야 한다.

입력
첫째 줄에는 수열의 길이 N이 주어지고, 둘째 줄에는 N개의 숫자가 빈칸을 사이에 두고 주어진다. N은 1 이상 100,000 이하의 정수이다.

출력
첫째 줄에 가장 긴 길이를 출력한다.

출처 

 

 

 아이디어 및 주의 사항 

✔ 커지는 경우와 작아지는 경우 두 개로 나누어서 계산

1. 연속해서 증가하는 경우
 1) for문으로 인덱스 0부터 N-2까지 순회하며
 2) 해당 인덱스의 값 <= 인덱스+1의 값 비교
   - 같거나 증가한다면 길이 세기
   - 감소하는 구간이 나온다면 이전까지 구한 길이 값과 최대 길이를 비교하여 갱신
 3) 마지막까지 증가하다 끝나는 경우 고려

2. 연속해서 감소하는 경우
  1, 2) 동일

3. 출력
  1) N == 1일 경우를 고려하기 => 1이 나와야 한다고 함 ㅡㅡ 쳇
  2) 실제로 반환해야 하는 길이는 순회하며 구한 길이 + 1

 

N = int(input())
numbers = list(map(int, input().split()))

# 커지거나 작아지는 횟수(길이) + 가장 긴 길이
cnt = max_cnt = 0

# 연속해서 커지는 것
for idx in range(N-1):
    if numbers[idx] <= numbers[idx + 1]:
        cnt += 1
    else: # 감소하는 구간을 마주쳤을 때
        if max_cnt < cnt: # 최대 길이 vs 그동안 구한 길이
            max_cnt = cnt # 더 길면 갱신
        cnt = 0       # 감소로 바뀌면 무조건 길이 초기화
# 마지막 값까지 증가하다 끝났을 때
if max_cnt < cnt:  # 최대 길이 vs 그동안 구한 길이
    max_cnt = cnt  # 더 길면 더하고

# 연속해서 작아지는 것
cnt = 0 # 작아지는 거 세야하니까 cnt 초기화
for idx in range(N-1):
    if numbers[idx] >= numbers[idx + 1]:
        cnt += 1
    else: # 증가하는 구간을 마주쳤을 때
        if max_cnt < cnt: # 최대 길이 vs 그동안 구한 길이
            max_cnt = cnt # 더 길면 갱신
        cnt = 0       # 증가로 바뀌면 무조건 길이 초기화
# 마지막 값까지 감소하다 끝났을 때
if max_cnt < cnt:
    max_cnt = cnt

print(max_cnt+1)