코드

n = int(input())
arr = list(map(int, input().split()))
x = int(input())

# 투 포인터는 정렬이 필요함
# 그래야 조건별로 값의 크기를 똑바로 비교할 수 있음
arr.sort()

# 시작과 끝 인덱스
start = 0
end = n-1

# 최종 정답 변수
cnt = 0

while start < end:
    
    # 합이 x가 되면 개수를 1 증가
    # 다음 start의 비교를 위해 1 증가
    if (arr[start] + arr[end]) == x:
        cnt += 1
        start += 1
    
    # 두 합이 x보다 작으면 start를 1 증가
    # 오름차순 정렬이므로 start가 1 증가하면
    # 해당 값 역시 증가한다 => x와 더 가까워짐
    elif (arr[start] + arr[end]) < x:
        start += 1
    
    # 두 합이 x보다 크면 end를 1 감소
    # end가 감소해야 start가 그대로일 때 값을 줄일 수가 있음
    else:
        end -= 1
    
print(cnt)

문제 해설

투 포인터를 활용한 문제.

이진 탐색과 매우 유사한 느낌의 알고리즘이다. 알고리즘의 이름에서 알 수 있듯이 리스트에서 두 개의 점을 찍어 두 점을 가운데로 점점 모아가면서 원하는 결과를 얻게 해주는 알고리즘이다.

간단한 로직은 아래와 같다.

  1. 주어진 리스트를 오름차순 정렬한다.
  2. 첫 번째 인덱스(start)와 마지막 인덱스(end)를 각각 변수에 저장한다.
  3. 첫 번째 요소와 마지막 요소의 합이 X와 같은지 비교한다.
    • 같다면 개수 1 증가
    • 크다면 end 1 감소 (마지막 요소가 가장 크므로 그 앞 요소는 이보다 작음)
    • 작다면 start 1 증가 (첫 요소가 가장 작으므로 그 뒷 요소는 이보다 큼)
  4. 3의 과정을 start가 end보다 커질 때까지 반복한다.

주어진 리스트의 요소 중 2개를 뽑아 합이 X가 되게 만드는 것이 문제의 목표인데, 단순히 생각해봐도 이를 최대한 중복없이 검사하려면 리스트를 정렬해야겠다는 것이 직감적으로 떠올랐다. 처음 이 알고리즘을 접했을 때는 정말 알겠으면서도 막막한 느낌이었는데, 이진 탐색을 어느정도 연습한 상태여서 그런지 생각보다 쉽게 이해가 갔다. 앞으로 이런 성취감을 느낄 수 있도록 더더욱 열심히 문제를 풀어야겠다.


투 포인터란?


리스트에 두 개의 점의 위치를 기록하면서 순차적으로 접근하여 원하는 결과를 얻는 알고리즘

블로그 참고

댓글남기기

참고