[코드트리 챌린지] 6주차 - 투포인터

0) 들어가기 앞서

지난 5주차 DP유형을 원할하게 풀이하지 못해 이번주차도 동일 유형을 학습하게 될 것이라 생각했다. 그러나 예상과는 다른 결과가 나타났는데..

1) 실력 진단 결과

IM단계의 TwoPointer유형을 학습하라는 진단을 받았다. 운좋게 실력진단 문항의 난이도가 쉽게 나왔던 것 같다. (지난 실력진단에서 통과하지 못했던 DP/이등변삼각형 문항이 출제되지 않았다.) 실력 진단 과정에서 Math, tuple, dictionary(key, value 해체), Counter, 순열/조합 관련된 내용을 검색하여 풀이했다. 참고했던 내용은 하단에 별도로 정리해보자!

리뷰

• Math.comb()
  (링크 : https://www.w3schools.com/python/ref_math_comb.asp)
• tup = (1, 2, 3) s = ''.join(map(str, tup)) (5주차 학습 내용 참고)
• 리스트 내 요소의 종류 및 개수 (링크 : https://bramhyun.tistory.com/55)
• 딕셔너리 for loop (링크 : https://wikidocs.net/16043)

2) 투 포인터

구간을 가리키는 시작 포인터와 끝 포인터가 한 방향으로만 전진하는 형태를 투 포인터(Two Pointer) 라고 한다.

주어진 리스트를 이중 for문으로 시간복잡도 O(n^2)에 풀이가 가능했다.

# 시작 포인터 반복
for i in range(n):
   # 끝 포인터 반복
   for j in range(i, n):

이를 2개의 포인터를 움직여서 2개의 반복문을 사용해 시간복잡도 O(n)으로 해결하는 알고리즘이 투 포인터 이다.

# 시작 포인터 반복
for i in range(n):
   # 구간 조건을 충족하도록 j를 반복 전진
   while j범위조건 and 구간조건:
      j += 1
   if 조건을 충족한다면:
      # 일련의 처리
      break
   # 다음 시작 포인터(i+1)를 탐색하기 전에 array[i] 값은 구간에서 제외

문제 1

• 0에 가장 가까운 합 (링크 : https://www.codetree.ai/missions/8/problems/sum-closest-to-zero?&utm_source=clipboard&utm_medium=text)

리뷰

• 가장 먼저 주어진 리스트를 정렬해야 한다. 오름차순으로 정렬했음을 가정해보자. 시작 인덱스가 i일 때, 끝 인덱스 j가 증가할수록(뒤쪽으로 갈수록) 합은 반드시 커진다.
• 즉, 시작 인덱스 i가 증가하면, 두 값의 합은 커지고, 종료 인덱스 j가 감소하면, 두 값의 합은 작아진다.
• 목표로 하는 것이 0에 가까워지는 것이기에, 두 값의 합이 0보다 크면 작아지게 만들기 위해 j를 감소시키고, 두 값의 합이 0보다 작으면 커지게 만들기 위해 i를 증가시켜야 한다. (참고 링크 : https://eda-ai-lab.tistory.com/434)
• 위 과정을 반복하며, 두 값의 합의 절댓값의 최소값을 갱신해준다. Python 코드로 구현하면 아래와 같다.

import sys
n = int(input())
arr = list(map(int, input().split()))
arr.sort()

abs_ans = sys.maxsize
i, j = 0, n-1

while i < j:
    sum_value = arr[i] + arr[j]
    abs_ans = min(abs_ans, abs(sum_value))

    if sum_value < 0:
        i += 1
    else:
        j -= 1

print(abs_ans)

문제 2

• 최소가 되는 좌표 범위의 차 (링크 : https://www.codetree.ai/missions/8/problems/the-minimum-difference-in-coordinate-range?&utm_source=clipboard&utm_medium=text)

리뷰

• 이중 for문으로 시도하였으나 N의 개수가 20,000 개를 넘어가면서 부터 시간초과가 발생하였고, Two Pointers 기법으로 해결되지 않아 풀이를 열어보았다.

# 잘못된 나의 풀이

import sys
N, D = map(int, input().split())
_list = [tuple(map(int, input().split())) for _ in range(N)]  # (2 4) (4 10) (6 3) (12 15)
_list.sort()

min_differ = sys.maxsize

for start in range(len(_list)-1):
    for end in range(start+1, len(_list)):
        if D <= abs(_list[start][1] - _list[end][1]):
            min_differ = min(min_differ, _list[end][0] - _list[start][0])
            break

        if _list[end][0] - _list[start][0] >= min_differ:
            break

    
print(-1 if min_differ == sys.maxsize else min_differ)