주몽 - 실버 4 (백준, 투포인터)

import sys
input = sys.stdin.readline

n = int(input())
m = int(input())
nums = list(map(int,input().split()))

nums.sort()
left, right = 0, len(nums) - 1
count = 0

while left < right:
    sum_num = nums[left] + nums[right]
    if sum_num < m:
        left += 1
    elif sum_num > m:
        right -= 1
    else:
        count += 1
        left += 1
        right -= 1

print(count)

 

투 포인터를 알면 굉장히 효율적으로 풀 수 있다.

 

문제를 풀때 "두 개의 재료로 만든다는 것에 주의하자."

 

특정한 합을 가지는 부분 연속 수열 찾기: 문제 해결 아이디어

• 투 포인터를 활용하여 다음과 같은 알고리즘으로 문제를 해결할 수 있다
  1. 시작점(start)과 끝점(end)이 첫 번째 원소의 인덱스(0)를 가리키도록 한다
  2. 현재 부분 합이 M과 같다면, 카운트한다
  3. 현재 부분 합이 M보다 작다면, end를 1 증가시킨다
  4. 현재 부분 합이 M보다 크거나 같다면, start를 1 증가시킨다
  5. 모든 경우를 확인할 때까지 2번부터 4번까지의 과정을 반복한다

• 𝑀 = 5
• [초기 단계] 시작점과 끝점이 첫 번째 원소의 인덱스를 가리키도록 한다
  • 현재의 부분합은 1이므로 무시한다
  • 현재 카운트: 0

• [Step 1] 이전 단계에서의 부분합이 1이었기 때문에 end를 1 증가시킨다
  • 현재의 부분합은 3이므로 무시한다
  • 현재 카운트: 0

• [Step 2] 이전 단계에서의 부분합이 3이었기 때문에 end를 1 증가시킨다
  • 현재의 부분합은 6이므로 무시한다
  • 현재 카운트: 0

• [Step 3] 이전 단계에서의 부분합이 6이었기 때문에 start를 1 증가시킨다
  • 현재의 부분합은 5이므로 카운트를 증가시킨다
  • 현재 카운트: 1

• [Step 4] 이전 단계에서의 부분합이 5이었기 때문에 start를 1 증가시킨다
  • 현재의 부분합은 3이므로 무시한다
  • 현재 카운트: 1

• [Step 5] 이전 단계에서의 부분합이 3이었기 때문에 end를 1 증가시킨다
  • 현재의 부분합은 5이므로 카운트를 증가시킨다
  • 현재 카운트: 2

• [Step 6] 이전 단계에서의 부분합이 5이었기 때문에 start를 1 증가시킨다
  • 현재의 부분합은 2이므로 무시한다
  • 현재 카운트: 2

• [Step 7] 이전 단계에서의 부분합이 2였기 때문에 end를 1 증가시킨다
  • 현재의 부분합은 7이므로 무시한다
  • 현재 카운트: 2

• [Step 8] 이전 단계에서의 부분합이 7이었기 때문에 start를 1 증가시킨다
  • 현재의 부분합은 5이므로 카운트를 증가시킨다
  • 현재 카운트: 3

https://freedeveloper.tistory.com/393

[이것이 코딩 테스트다 with Python] 39강 투 포인터