접근

이전 투포인터 알고리즘 문제들이 좌우 끝에서 가운데서 만날 때까지 연산했다면 이번 문제에서는 두 점이 0,0 으로 시작하여 마지막 점에 도달할 때까지 계산을 해주었다.

투포인터 알고리즘 설명 및 기본문제: 2021.04.24 - [코딩/백준 (Python)] - 백준 3273번: 두수의 합 (Python)

 

백준 3273번: 두수의 합 (Python)

접근 먼저 투포인터 알고리즘에 대해 알아보았다. 위 문제를 가장 직관적인 방법으로 푸는 방법은 2중 for문을 순환하면서 두 수의 합이 원하는 값을 표시할때마다 카운트해주는 것이다. 하지만

ca.ramel.be

두개의 점 left 와 right 이 각각 0, 0 에서 시작하여 left 에서 right 까지의 부분합이 s를 넘는지 체크하여 다음과 같이 계산한다.

  1. left 에서 right 까지의 부분합이 s보다 작을 경우 right 를 1 늘려준다. (부분 수열이 길어지고 부분합이 커진다.)
  2. left 에서 right 까지의 부분합이 s보다 클 경우 부분 수열의 길이를 갱신하고 left를 1 늘려준다. (부분 수열이 짧아지고 부분합이 작아진다.)

코드

import sys

n, s = map(int, sys.stdin.readline().split())
nums = list(map(int, sys.stdin.readline().split()))

length = float('inf')
left, right = 0, 0
tmp = nums[left]
while 1:
    if tmp < s:
        right += 1
        if right == n:
            break
        tmp += nums[right]
    else:
        length = min(length, right - left + 1)
        tmp -= nums[left]
        left += 1
print(0 if length == float('inf') else length)

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!

반응형
  • 네이버 블러그 공유하기
  • 네이버 밴드에 공유하기
  • 페이스북 공유하기
  • 카카오스토리 공유하기