시간이 없는 분들을 위해 최종 제출물을 먼저 보여주고 이후에 얘기를 풀겠다. 내가 블로그 하면서 항상 답답했던거는 내가 원하는 정보를 꼭 찾아가야한다는것.. 이렇게 함으로써 다른분들은 답답함이 없었으면 좋겠다.
# 리스트 갯수 N과 연속적인 날자 수 K 할당
N, K=map(int, input().split())
# 두번째 input 값을 공백을 기준으로나눈 list 할당
tem_lst=list(map(int, input().split()))
first_num=0# 데이터를 비교하기 위한 첫 K까지의 합을 할당하기 위한 초기 설정
foriinrange(K): #index기준으로 0부터 K-1 까지 계산.
first_num+=tem_lst[i] #i가 k-1까지 돈 list의 데이터들을 다 first_num에 더해준다.
max_num=first_num#비교를 위해 첫 K개의 데이터 합을 max_num으로 설정해준다.
forjinrange(K, N): #index기준으로 K부터 리스트의 > 방향으로 한칸씩 밀어 N-1 까지 비교한다.
first_num=first_num+tem_lst[j] -tem_lst[j-K] # tem_lst[j] : 오른쪽 데이터, tem_lst[j-K] : 왼쪽데이터
ifmax_num<=first_num: # 비교 후 큰 값 재할당
max_num=first_num
print(max_num) #출력
이거를 몇일동안 잡고 있었는지.. 1주일은 고민했다가 말았다가 한거같은데 결국 스터디원의 코드를 보고 아이디어를 얻어왔다. 블로그에 이론만 정렬하기엔 시간도 많지 않고, 문제를 설계하는 연습과 오답노트를 위해 백준 문제 풀이들을 올려보려 한다.
문제에 대해 간단하게 설명하자면, N개의 정수 데이터가 주어지고, 연속된 K개 데이터 합을 구하는 것이다. 되게 간단해보이지만, 상대는 백준. 사람이다. (기계인가?)
가장 먼저 실수를 하는 것 중에 하나는 sort를 해서 최댓값들의 연속된 K개 데이터 합을 구하는 것인데, 이는 초기 주어진 리스트를 변형하는 것이기 때문에 문제에서 요구하는 사항에 맞지 않아 바로 틀렸습니다를 선언해준다.
그래서 이해를 하기위해 아래의 초기 스케치를 시작해봤는데, 되게 멋진 사람 된 것 같았다.
문제 이해와 방향을 정하기 위한 초기 스케치
나는 데이터들을 토너먼트 시킨다고 이해를 했고, 그렇다면 토너먼트한 요소들을 새로운 리스트에 뽑아와서 그 중에 max()함수를 돌려 최댓값을 가져오려 했었다.
분홍색 글씨의 풀이 2를 확인해보면, 2중 반복문을 통해 i에서 i+k의 값을 더한 데이터들을 새로운 리스트에 할당한다고 계획 한 것을 볼 수 있다. 그 결과 정확한 반환을 할 수 있었고 자신있게 제출을 했다.
# 리스트 갯수 N과 연속적인 날자 수 K 할당
N, K=map(int, input().split())
# 두번째 input 값을 공백을 기준으로나눈 list 할당
tem_lst=list(map(int, input().split()))
# 2-1 lst[0] + lst[1] + ... lst[k] 까지 합을 할당
# 새로운 리스트를 만들어서 수열 값을 할당을 더한다 (시간초과)
foriinrange(0, N-K+1):
tem_sum=0
forjinrange(i, i+K):
tem_sum+=tem_lst[j]
new_lst += [tem_sum]
print(max(new_lst))
가차없이 시간초과를 때려버리는...
위의 코드가 가장 처음 짰던 문제다. 확인해보면 2중for문을 사용하고 있는 것을 볼 수 있고 %가 굉장히 천천히 올라가다가 바로 가차없이 뱉어버리더라.
물론 5일전에 풀때만해도 2중 반복문 관련해서 시간 복잡도라던가 그런 내용을 몰랐기 때문에 내가 코드를 틀렸나보다 했는데, 스터디원에게 물어보니 답은 맞다고 하더라. 같은 결과를 보고 이후에 수정했다고하던데, 나는 아직은 혼자 공부하고싶어서 답을 미루었다.
# 리스트 갯수 N과 연속적인 날자 수 K 할당
N, K=map(int, input().split())
# 두번째 input 값을 공백을 기준으로나눈 list 할당
tem_lst=list(map(int, input().split()))
# 2-2 리스트에 할당하지 않고 for문의 sum_num과 max_sum을 바로 비교 후 출력 (시간초과)
max_sum=0
foriinrange(0, N-K+1):
sum_num=0
forjinrange(i, i+K):
sum_num+=tem_lst[j]
ifmax_sum<=sum_num:
max_sum=sum_num
print(max_sum)
이제 그만해..... 죽여줘.....
처음엔 리스트를 생성하는게 그렇게 오래걸리나 해서 리스트에 따로 할당하지 않고 바로 다음 sum값과 비교해서 제출했는데... 또 뱉더라... 사실 3번 더 시행착오가 있었는데 비슷한 내용이라 생략하겠다.
결국 다른 친구의 도움을 받기 위해 힌트를 부탁했고 2중 for문의 시간이 오래걸리고, 한번으로도 충분히 가능하다고 했다. 심지어 내 코드에서 조금만 개선하면 된다고 해서 고민을 많이 했다.
그 결과 한번의 for문으로 만든다고 한다면 데이터의 앞과 뒤를 설정하면 된다고 생각했다. 지렁이가 꿈틀 기어가는것처럼 오른쪽으로 한칸가면 왼쪽의 한칸을 빼는느낌으로 말이다. 그러한 기준으로 아래와 같은 코드가 나오게 되었다. 사실 깔끔한 코드는 아니지만, 내 기준 당시의 최선이다.
# 리스트 갯수 N과 연속적인 날자 수 K 할당
N, K=map(int, input().split())
# 두번째 input 값을 공백을 기준으로나눈 list 할당
tem_lst=list(map(int, input().split()))
first_num=0# 데이터를 비교하기 위한 첫 K까지의 합을 할당하기 위한 초기 설정
foriinrange(K): #index기준으로 0부터 K-1 까지 계산.
first_num+=tem_lst[i] #i가 k-1까지 돈 list의 데이터들을 다 first_num에 더해준다.
max_num=first_num#비교를 위해 첫 K개의 데이터 합을 max_num으로 설정해준다.
forjinrange(K, N): #index기준으로 K부터 리스트의 > 방향으로 한칸씩 밀어 N-1 까지 비교한다.
first_num=first_num+tem_lst[j] -tem_lst[j-K] # tem_lst[j] : 오른쪽 데이터, tem_lst[j-K] : 왼쪽데이터
ifmax_num<=first_num: # 비교 후 큰 값 재할당
max_num=first_num
print(max_num) #출력
이렇게되면 for문 하나 안에서 이동하면서 if문을 통해 최댓값을 계속 비교해줄 수 있더라. 자세한 설명은 주석으로 추가해놓았다. 다만 주의해야할 점은 범위 설정인데, range(K, N)부분을 주의해서 봐줬으면 좋겠다. 항상 헷갈리는 부분인데, 데이터를 리스트의 index로서 접근하기 때문에 마무리부분은 항상 중요하다는점. 고작 1차이로 항상 list out of range를 흔히 볼 수 있을 것이다. 아직 2차원 배열을 배우지도 않았는데.. 걱정이 많다.
