[코드트리 챌린지] 4주차 - Two Pointer

지난 주와 비슷한 문제에서 틀려 같은 점수를 받았습니다. 곧 있을 삼성 sw 역량 평가에 대비한다고 구현 문제를 위주로 풀었더니.. +1 -1, two pointer와 같은 테크닉이 새롭게 보이더라구요..!

 

그래서 이번주는 Two Pointer에 대해 개념을 다시보고 문제를 풀어보았습니다. 다른 코딩 테스트 뿐만 아니라, 효율적인 탐색을 하는데 있어 자주 등장하는 유형이므로 꼭 이번 기회에 마스터하겠습니다.

 

https://www.codetree.ai/missions/8/problems/shortest-subtotal?&utm_source=clipboard&utm_medium=text

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

합이 S이상이 되는 범위 중 최소 범위를 찾는 문제였습니다.

 

투포인터 풀 때 항상 헷갈렸던 부분이 초기에 left와 right포인터의 인덱스를 어디 둘지가 어려웠는데 앞에 [0]과 같이 합에 영향을 주지 않는 값을 추가해주면 해결되는 문제였습니다 :)

 또한 문제 해설을 참고하면 for문으로 푼 것도 있으니 어려우신 분들은 바로 고고!!

 

다양한 유형을 익혀두면 나중에 어떤 문제를 만나도 쉽게 아이디어를 떠올릴 수 있으니 다들 목표한 수준까지 화이팅입니다 :D

N, S = map(int, input().split())
nums = [0] + list(map(int, input().split()))
left = 0
right = 1
val = nums[right]
result = float('inf')
while right < N and left <= right:
    if val >= S:
        result = min(result, right-left+1)
        val -= nums[left]
        left += 1
    else:
        right += 1
        if right < N:
            val += nums[right]
print(result if not result == float('inf') else -1)