[투 포인터] 두 수의 합

[ericagong]

⭐ 성찰

1. 시간 복잡도를 먼저 계산하여, 완전 탐색이 좋은지 투포인터로 풀어야하는지 확인하기
2. ⭐ 투 포인터로 풀이 시, 반드시 사전에 정렬되어 있는 배열 여야 중반에 탈출 가능. ⭐
3. ⭐ 투 포인터의 종료 조건은 주로, si >= ei 임. 즉, 두 포인터가 겹치는 경우 종료됨. ⭐

❓ 문제 상황

두 수의 합

👨‍💻 문제 해결

✅ 1차 풀이: 완전 탐색

1. 모든 경우의 수를 계산해서 cnt 구하기

const fs = require("fs"); const inputs = fs.readFileSync("/dev/stdin").toString().split("\n");

const n = Number(inputs.shift()); const nums = inputs.shift().split(" ").map(Number); const x = Number(inputs.shift());

let cnt = 0; for (let si = 0; si < nums.length - 1; si++) { for (let ei = si + 1; ei < nums.length; ei++) { if (nums[si] + nums[ei] === x) cnt += 1; } }

console.log(cnt);

### ✅ 2차 풀이: 투 포인터
1. 우선, 배열을 오름차순 정렬
2. 배열의 좌/우 맨 끝에 si, ei 설정하여 포인터가 가리키는 원소의 합이 x보다 크거나 같을 경우 ei를 줄임
ㄴ 이 때, ei가 0이 되지 않도록 주의
```javascript
const fs = require('fs')
const inputs = fs.readFileSync('/dev/stdin').toString().split('\n')

const n = Number(inputs.shift())
const nums = inputs.shift().split(' ').map(Number)
const x = Number(inputs.shift())

nums.sort((a, b) => a - b) // 숫자 오름차순 정렬

let si = 0
let ei = n - 1
let cnt = 0
while(true) {
  while(ei > si && nums[si] + nums[ei] >= x) {
    if(nums[si] + nums[ei] === x) cnt += 1
    ei -= 1
  } 
  si += 1
  if(si >= ei) break // 서로 다른 두 개의 정수를 고르는 조합임
}

console.log(cnt)

[ericagong]

⌛ 완전 탐색과 투포인터 풀이의 시간 차이

• 상단 풀이가 투포인터, 하단 풀이가 완전 탐색