몸과 마음이 건전한 SW 개발자

코드트리 | Two Pointer / 가장 짧은 부분합 {언어 : Python} [다시 풀어 보기] 본문

알고리즘/다시 풀어 보기

코드트리 | Two Pointer / 가장 짧은 부분합 {언어 : Python} [다시 풀어 보기]

스위태니 2024. 12. 31. 16:40

문제 링크

https://www.codetree.ai/missions/8/problems/shortest-subtotal/submissions

 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.

www.codetree.ai

내 코드

n, k = map(int, input().split())
nums = list(map(int, input().split()))
tot = nums[0]
answer = 100000
r = 0
for l in range(n):
    while r + 1 < n and tot < k:
        tot += nums[r+1]
        r += 1
    if tot >= k:
        answer = min(answer, r - l + 1)
    tot -= nums[l]
if answer == 100000:
    print(-1)
else:
    print(answer)

풀이 방법

  1. 두 포인터 초기화
    • 배열의 시작 지점을 가리키는 왼쪽 포인터 l과 끝 지점을 가리키는 오른쪽 포인터 r을 설정한다.
    • 처음에는 두 포인터가 배열의 첫 번째 원소를 가리킨다.
    • 현재 부분 배열의 합을 저장하는 변수 tot를 초기화한다.
  2. 오른쪽 포인터 이동 (확장)
    • 현재 부분 배열의 합 tot이 목표값 k보다 작으면, 오른쪽 포인터를 이동시켜 배열의 다음 원소를 포함한다.
    • 새로운 원소를 tot에 추가하여 현재 합을 갱신한다.
  3. 조건 만족 시 최소 길이 계산
    • 부분 배열의 합 tot이 k 이상이 되면, 현재 부분 배열의 길이를 계산한다.
      • 길이는 (오른쪽 포인터 - 왼쪽 포인터 + 1)로 구한다.
    • 계산한 길이를 기존의 최소 길이와 비교하여 더 짧은 값을 갱신한다.
  4. 왼쪽 포인터 이동 (축소)
    • 왼쪽 포인터를 이동하여 현재 부분 배열의 시작점을 변경한다.
    • 이때, 시작점이 빠지므로 tot에서 해당 값을 빼서 갱신한다.
    • 이렇게 하면 부분 배열의 길이를 줄이면서도 조건을 만족하는지 확인할 수 있다.
  5. 반복
    • 왼쪽 포인터를 배열의 끝까지 이동시키면서 위의 과정을 반복한다.
    • 오른쪽 포인터는 조건에 따라 계속 확장하거나 유지되므로, 배열 전체를 완전히 탐색할 필요 없이 효율적으로 작업이 이루어진다.
  6. 결과 출력
    • 만약 k 이상의 합을 가지는 부분 배열이 한 번도 없다면, 결과로 -1을 출력한다.
    • 그렇지 않다면, 최소 길이를 출력한다.

작동 예제

예제 배열

  • 배열: [5, 1, 3, 5, 10, 7, 4, 9, 2, 8]
  • 목표값: k = 15

과정

  1. 초기 상태: tot = 5, l = 0, r = 0.
  2. 오른쪽 포인터 이동: tot = 5 + 1 + 3 + 5 = 14, 조건 미충족.
  3. 계속 이동: tot = 14 + 10 = 24, 조건 충족 → 길이 계산 → 최소 길이 = 5.
  4. 왼쪽 포인터 이동: tot = 24 - 5 = 19, 조건 충족 → 길이 갱신 → 최소 길이 = 4.
  5. 반복: 최단 길이 = 2까지 갱신.

출력

  • 조건을 만족하는 부분 배열의 최소 길이: 2.

느낀점

  • 이렇게 계산한다는 것을 이제 알았다...
  • 아직 갈 길이 멀다.