백준 14921 문제 _ 투 포인터 알고리즘 (Two Pointers Alogorithm)

투 포인터 알고리즘

배열 또는 리스트에서 두 개의 포인터(인덱스) 사용하여 문제를 해결하는 알고리즘.

 

사용하는 상황

정렬된 배열에서 순회하거나 검색할 때 사용된다.

완전탐색 시간복잡도가 너무 클 때 생각해볼 수 있음.

단 정렬을 하고 사용해야 한다.  

시간 복잡도

O(N), O(logN)

 

예제

 

1. 정렬된 배열에서 두 숫자의 합이 특정한 값이 되는 두 숫자를 찾는 문제

function twoSum(nums, target) {
    let left = 0; // 배열의 시작에서 시작하는 포인터
    let right = nums.length - 1; // 배열의 끝에서 시작하는 포인터

    while (left < right) {
        const sum = nums[left] + nums[right];
        if (sum === target) {
            return [left, right]; // 두 숫자의 합이 target과 같으면 인덱스 반환
        } else if (sum < target) {
            left++; // 두 숫자의 합이 작으면 왼쪽 포인터를 이동
        } else {
            right--; // 두 숫자의 합이 크면 오른쪽 포인터를 이동
        }
    }

    return null; // 목표를 달성할 수 없는 경우 null 반환
}

// 예제 사용법:
const nums = [2, 7, 11, 15];
const target = 9;
const result = twoSum(nums, target);
console.log(result); // [0, 1] (nums[0] + nums[1] = 2 + 7 = 9)

 

 

2. 정렬된 배열에서 두 숫자의 합 경우의 수 중,  0과 가장 가까운 합을 찾는 문제

백준 14921

const fs = require('fs')
const inputDatas = fs.readFileSync('./input.txt').toString().trim().split('\n')

const n = parseInt(inputDatas[0])
let nums = inputDatas[1].split(' ').map(data => parseInt(data)).sort((a,b)=> a-b)

let result = 200000000
let ans = 0
function difference(check) {
    return Math.abs(check)
}

// 투포인터 탐색
let left = 0
let right = nums.length - 1

while(left < right) {
    let tmp = nums[left] + nums[right]
    // 음수인 경우 right를 더 내리면 더 큰 음수가 된다 -> left 올리기
    if (tmp < 0) {
        left += 1
        let tmpResult = difference(tmp)
        // console.log(tmpResult,"tempResmp")
        if (tmpResult < result) {
            result = tmpResult
            ans = tmp
        }
    }
    // 양수인 경우 left를 올리면 더 큰 양수가 된다 -> right 내리기
    else if (tmp > 0) {
        right -= 1
        let tmpResult = difference(tmp)
        if (tmpResult < result) {
            result = tmpResult
            ans = tmp
        }

    }
    else if (tmp == 0) {
        ans = tmp
        break
    }
}
console.log(ans)