# 숫자 리스트가 주어질 때
# 합이 K가 되는 두 숫자가 있는지 찾아보자.

arr = [1, 2, 3, 5, 7, 9]
K = 10

# 👉 리스트는 이미 정렬되어 있다고 가정한다.
# (투포인터는 보통 "정렬된 리스트"에서 사용한다)

# ============================================
# 3. 투포인터 준비
# --------------------------------------------
# left  : 왼쪽에서 시작하는 포인터
# right : 오른쪽에서 시작하는 포인터

left = 0
right = len(arr) - 1

# ============================================
# 4. 투포인터 핵심 규칙
# --------------------------------------------
# 1) 두 값을 더한다
# 2) 합이 K와 같으면 → 성공
# 3) 합이 K보다 작으면 → left를 오른쪽으로 이동
# 4) 합이 K보다 크면 → right를 왼쪽으로 이동
#
# ❗ 중요한 점
# 포인터는 한 번 이동한 곳으로 다시 돌아오지 않는다.

# ============================================
# 5. 투포인터 실행
# --------------------------------------------

found = False   # 정답을 찾았는지 기록하는 변수

while left < right:
    # 현재 두 포인터가 가리키는 값의 합
    s = arr[left] + arr[right]

    # 현재 상태 확인
    print("left:", left, "right:", right, "합:", s)

    if s == K:
        print("정답 발견:", arr[left], arr[right])
        found = True
        break

    elif s < K:
        # 합이 작으면 더 큰 값을 만들기 위해 left 이동
        left += 1

    else:
        # 합이 크면 더 작은 값을 만들기 위해 right 이동
        right -= 1

# ============================================
# 6. 결과 정리
# --------------------------------------------

if not found:
    print("합이", K, "인 두 수가 없습니다.")

# ============================================
# 7. 이중 반복문과 비교 (개념 정리용)
# --------------------------------------------
# 이중 반복문은 모든 경우를 전부 비교한다.
#
# for i in range(len(arr)):
#     for j in range(i+1, len(arr)):
#         if arr[i] + arr[j] == K:
#             print(arr[i], arr[j])
#
# 👉 쉽지만 느림 (O(N^2))
# 👉 투포인터는 빠르고 효율적 (O(N))

# ============================================
# 8. 오늘의 핵심 한 문장
# --------------------------------------------
# 투포인터는 배열에 손가락 두 개를 놓고
# 조건에 따라 필요한 방향으로만 이동하며
# 불필요한 비교를 줄이는 방법이다.