[실버 IV] 2491번. 수열

 문제 

https://www.acmicpc.net/problem/2491

2491번: 수열

 사용 언어 

Python3

 풀이 과정 

'구현 + 다이나믹 프로그래밍'을 주제로 스터디 팀원들이 골랐던 문제인데 DP라고 생각해서 더 어려웠던 것 같다.

 

처음에 내가 DP를 이용해 푼 코드는 다음과 같다.

from sys import stdin
input = stdin.readline

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

maxlength = [1 for _ in range(N)]
minlength = [1 for _ in range(N)]
for i in range(1, len(sequence)):
    if sequence[i-1] <= sequence[i]:
        maxlength[i] = max(maxlength[i-1] + 1, maxlength[i])
    if sequence[i-1] >= sequence[i]:
        minlength[i] = max(minlength[i-1] + 1, minlength[i])

print(max(max(maxlength), max(minlength)))

max를 여러번 반복하기 때문에 최적의 코드는 아닐 것 같았다.

한 번에 맞았습니다!!를 봤지만 역시 다른 코드들과 비교했을 때 시간 복잡도가 좋지 않아서 마음에 들지 않았다.

따라서 아래 다른 코드들을 보며 공부한 것들을 내 코드에 적용해 최종적으로 제출 답안은 아래와 같다.

 제출 답안 

from sys import stdin
input = stdin.readline

def calcLength(seq):
    count = 1
    maxCount = 1
    for i in range(N-1):
        if seq[i] <= seq[i+1]:
            count += 1
        else:
            if count > maxCount:
                maxCount = count
            count = 1
    if count > maxCount:
        maxCount = count
    return maxCount

if __name__ == "__main__":
    N = int(input())
    sequence = list(map(int, input().split()))
    print(max(calcLength(sequence), calcLength(sequence[::-1])))

 다른 사람 코드 

일단  맞힌 사람 에서 시간 순으로 상위에 있는 코드들은 모두 DP를 사용하지 않았다. DP를 사용하지 않고도 충분히 풀 수 있는 문제인데 태그를 보고 괜히 더 어렵게 생각한 것이지...

 

1. 줄어드는 수열의 max값을 원래 수열을 뒤집은 순서에 같은 함수를 적용해 구한 코드

n=int(input())
seq=list(map(int,input().split()))

def f(seq):
    cnt=1
    max_cnt=0
    for idx in range(n-1):
        if seq[idx]<=seq[idx+1]:
            cnt+=1
        else:
            if cnt>max_cnt:
                max_cnt=cnt
            cnt=1
    if cnt>max_cnt:
        max_cnt=cnt
    return max_cnt

print(max(f(seq),f(seq[::-1])))

➡ 이런 생각은 어떻게 하는거야... 줄어드는 수열은 당연히 부등호를 뒤집을 생각을 하지 수열 자체를 뒤집을 생각을 하다니..! 이런 아이디어는 기억해두고 다른 문제에서 써먹을 수 있으면 써먹어야겠다.

 

2.  next( ) 를 사용한 게 신기했던 코드, prev 변수는 iterator[0] 값으로 초기화된다.

import sys
N = int(input())
iterator = map(int,sys.stdin.readline().split())
prev = next(iterator)
inc_cnt = 1
dec_cnt = 1
max_inc_cnt = 1
max_dec_cnt = 1
for val in iterator:
    dec_cnt += 1
    inc_cnt += 1
    if prev < val:
        if max_dec_cnt < dec_cnt:
            max_dec_cnt = dec_cnt - 1
        dec_cnt = 1
    elif prev > val:
        if max_inc_cnt < inc_cnt:
            max_inc_cnt = inc_cnt - 1
        inc_cnt = 1
    prev = val

print(max(max_dec_cnt,max_inc_cnt, dec_cnt, inc_cnt))

➡ 제일 적은 메모리와 시간을 사용한 코드. 추가로 나였다면 iterator 변수의 경우 무조건 list( )로 한 번 더 감싸줬을텐데 그냥 map 객체 그대로 for문을 돌리는 것도 배운 점이다.