[BaekJoon] 2559번 : 수열 (Python)

코딩 1일 1문제! 오늘의 문제는 백준의 2559번 수열 입니다.

임인년 새해의 2번째날! 모두 새해 복 많이 받으시기 바랍니다~!

2559번: 수열

👨🏻‍💻 문제 풀이

백준 2529번 수열.

사실 엄청 쉬워보여서 빨리 풀고 신세계 백화점으로 미디어 파사드 구경가야지~ 라고 생각했다가 큰 코 다친 문제입니다.

N일 동안 측정한 온도 리스트(수열)( temperature_list ) 과 K 값을 입력 받으면

연속적인 K일 온도의 합의 최대값을 구하는 문제입니다.

 

위의 그림의 경우에는 10일 동안 측정한 온도리스트에서 연속적인 2일 온도의 합을 모두 구한 모습이며

위의 그림에서 정답은 [1, -6, -13, -0, 3, 10, 20, 21, 5] 여기서 최대값인 21 입니다.

먼저 예제 입력을 확인하고 데이터를 입력 받는 부분부터 코드를 작성하였습니다.

N, K = map(int, input().split())
temperture_list = list(map(int, input().split()))

입력받는 값은 공백을 기준으로 정수들이 줄줄이 나오는 문자열인데

이를 각각 정수값들로 바꾸어야 하여 map(int, input().split())를 활용하여 

입력 받은 값을 공백 기준으로 나눈 다음 정수 형식으로 바꾸어 주도록 하였습니다.

😎 첫번째 시도 - 시간초과

temp_k_days_list = []
for i in range(len(temperture_list) - K + 1):
    temp_k_days_list.append(sum(temperture_list[i:i+K]))

첫 시도로는 가장 쉬운 방법으로 입력 받은 K 개씩 slicing 하여 이를 sum으로 합을 구하여 list에 저장해 두었다가

max(temp_k_days_list)

그 값들 중 최대 값을 정답으로 하도록 풀어보았습니다.

결과는...! 뭔가 채점중 속도가 느리더니 역시나.. 시간초과 였습니다.

N이 100,000 이하라고 할 때 알아 봤어야 했는데 너무 쉽게 생각하고 문제를 풀기 시작했다! 라는 생각이 들었습니다.

아마 계속 sum을 N-K 번 하다보니 시간초과가 난 것 같아 다른 방법으로 풀어보기로 했습니다.

👨🏻‍💻 첫번째 시도 - 전체 코드

def sequence(temperture_list, K):
    temp_k_days_list = []
    for i in range(len(temperture_list) - K + 1):
        temp_k_days_list.append(sum(temperture_list[i:i+K]))
        
    return max(temp_k_days_list)

if __name__ == "__main__":
    N, K = map(int, input().split())
    temperture_list = list(map(int, input().split()))
    print(sequence(temperture_list, K))

😎 두번째 시도

이번에는 sum의 호출 횟수를 줄이기 위해서 맨 첫 번째 연속된 K일 온도의 합을 구해놓고

temp_k_days_list = [sum(temperture_list[:K])]

다음 연속된 온도의 합 = 바로 이전 연속된 온도의 합 + 다음 순번에서 K번째 온도 - 이전 연속된 날짜 중 가장 앞 날짜의 온도

로 구했습니다.

for i in range(1, len(temperture_list) - K + 1):
    sum_k_temp = temp_k_days_list[-1] + temperture_list[i+K-1] - temperture_list[i-1]
    temp_k_days_list.append(sum_k_temp)

 

그리고 최종 정답은 첫번째 시도와 같이 max를 통해 구했습니다.

위의 그림을 예시로 들어 이 방법에 대해서 쭉 풀어보면

온도 수열 = [3, -2, -4, -9, 0, 3, 7, 13, 8, -3]

첫 연속된 2일의 온도의 합 = 3 + -2 = 1

1 + -4 - 3 = -6
-6 + -9 - -2 = -13
-13 + 0 - -4 = -9
-9 + 3 - -9 = 3
3 + 7 - 0 = 10
10 + 13 - 3 = 20
20 + 8 - 7 = 21
21 + -3 - 13 = 5

연속된 2일의 온도의 합 = [1, -6, -13, -9, 3, 10, 20, 21, 5]

여기서 최대값 = 21

위와 같이 풀어지는 것을 볼 수 있습니다.

 

제출 결과는...!

이번엔 시간 초과가 아닌 맞았습니다!! 를 볼 수 있었습니다.

 

전체 코드는 아래를 참고해주세요.

👨🏻‍💻 코드 ( Solution )

def sequence(temperture_list, K):
    temp_k_days_list = [sum(temperture_list[:K])]
    for i in range(1, len(temperture_list) - K + 1):
        sum_k_temp = temp_k_days_list[-1] + temperture_list[i+K-1] - temperture_list[i-1]
        
        temp_k_days_list.append(sum_k_temp)
        
    return max(temp_k_days_list)

if __name__ == "__main__":
    N, K = map(int, input().split())
    temperture_list = list(map(int, input().split()))
    print(sequence(temperture_list, K))

GitHub - SOMJANG/CODINGTEST_PRACTICE: 1일 1문제 since 2020.02.07