[BOJ | Python] 2491번: 수열

https://www.acmicpc.net/problem/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 이하의 정수이다.

 

 

출력

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

 

 

풀이

input = __import__('sys').stdin.readline
N = int(input())
arr = list(map(int, input().split()))
dp_big, dp_small = [1] * N, [1] * N

for i in range(1, N):
    if arr[i - 1] <= arr[i]:
        dp_big[i] = dp_big[i - 1] + 1
    if arr[i - 1] >= arr[i]:
        dp_small[i] = dp_small[i - 1] + 1

print(max(max(dp_big), max(dp_small)))

문제에서 연속해서 커지거나 혹은 연속해서 작아지는 수열의 길이를 구하라고 했으므로, 연속해서 커지고 연속해서 작아지는 각각의 길이를 저장할 배열 dp_big, dp_small을 생성한다.

(이때 만약 dp_big = dp_small = [1] * N 이런식으로 초기화를 하면 두 배열이 같은 참조를 가지게 되어 답이 안 나온다... 나같은 바보같은 실수 하지 마시길)

 이후 바로 직전 배열의 값과 현재 배열의 값을 비교하며 크면 dp_big에 값을 저장하고, 작다면 dp_small에 값을 저장하였다.

- dp 배열을 1로 초기화하였기 때문에 위 경우가 아니라면 따로 값을 저장하지 않아도 된다.

이후 두 Dp 배열에서 최댓값을 찾아 출력하였다.

max를 중첩으로 쓰는 게 시간초과가 나진 않을까 걱정했는데 pypy3으로 제출해서 그런지 한 번에 통과할 수 있었다!