99클럽 코테 스터디 _ 5일차 TIL (투 포인터)

 

< 문제 >

[백준] 2470. 두 용액 / 골드5

---

< 풀이 >

코드 변수 정의

• liquids : 가지고 있는 랜선 길이 리스트
• min_diff : 두 용액의 합 중 0에 가까운 값
• liquid_sum : 현재 선택된 두 용액의 합

---

Two Pointers
시간복잡도 : O(N)

def binary_search(liquids, N):
    left, right = 0, N - 1
    min_diff, ans = float('inf'), [0, 0]

    while left < right:
        liquid_sum = liquids[left] + liquids[right]
        if min_diff > abs(liquid_sum):
            min_diff = abs(liquid_sum)
            ans = [liquids[left], liquids[right]]
        if liquid_sum < 0:
            left += 1
        else:
            right -= 1

    return ans

def f():
    N = int(input())
    liquids = sorted(list(map(int, input().split())))
    print(*binary_search(liquids, N))

f()

• 투 포인터
  1. 투 포인터를 쓰기 위해서 용액의 특성값(liquids)을 오름차순으로 정렬한다.
  2. 두 용액의 합을 liquid_sum으로 지정하고
  3. 현재 특성값 합(min_diff) > abs(liquid_sum)
     • min_diff = abs(liquid_sum)
  4. liquid_sum이 음수인 경우
     • left += 1
  5. liquid_sum이 양수인 경우
     • right += 1

---

< 회고 >

투 포인터로 이중 for문을 사용하지 않고 부분합을 찾을 수 있는 방법에 대해 생각할 수 있었다.

 

 

Two Pointers

• 리스트에 순차적으로 접근할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘
• 시작점과 끝점 2개의 점으로 접근할 데이터의 범위를 표현할 수 있다.

 

(응용문제) _ 특정한 합을 가지는 부분 연속 수열 찾기

• 문제 설명
  • N개의 자연수로 구성된 수열이 있다.
  • 합이 M인 부분 연속 수열의 개수를 구하라
  • 수행 시간 제한은 O(N)

• 문제 해결 아이디어
  1. 시작점(start)과 끝점(end)이 첫 번째 원소의 인덱스(0)를 가리키도록 한다.
  2. 현재 부분 합이 M과 같다면, 카운트한다.
  3. 현재 부분 합이 M보다 작다면, end += 1
  4. 현재 부분 합이 M보다 크거나 같다면, start += 1
  5. 모든 경우를 확인할 때까지 2번부터 4번 과정을 반복한다.

 

 

---

참고

이것이 코딩 테스트다 with Python