백준 3273번 <두 수의 합>

백준 3273번 <두 수의 합>

실버 3

https://www.acmicpc.net/problem/3273

3273번: 두 수의 합

한 동안 프로젝트에 전념하다가 

오랜만에 알고리즘을 풀게 되었습니다.

 

이제 좀 알고리즘 별로 대비를 해볼까 해서 먼저 투포인터 알고리즘 관련 문제들을 풀어보았습니다.

const fs = require('fs');
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
let n = parseInt(input[0]);
let arr = input[1].split(" ").map(Number).sort((a, b) => a - b);
let x = parseInt(input[2]);

let l = 0;
let r = n - 1;
let answer = 0;

while (l !== r) {
    if (arr[l] + arr[r] == x) {
        answer++;
        r--;
    } else if (arr[l] + arr[r] < x) {
        l++;
    } else if (arr[l] + arr[r] > x) {
        r--;
    }
}

console.log(answer);

for문을 두 번 돌아도 되지만 

시간복잡도가 굉장히 커지면서 시간 초과가 나올 것 같더라구요.

 

일단 입력 받은 배열을 오름차순으로 정렬 하고 l (left) 변수를 맨 처음 인덱스 값(0)으로 초기화, r (right) 변수를마지막 인덱스 값(n-1)으로 초기화해주고 그 두 값을 더한 수와 x를 순차적으로 비교해줍니다.

그 둘을 더한 값이 x보다 크면  r값을 하나 빼주고, x보다 작으면 l값을 하나 더해주며, x와 같을 시에는

answer 값을 더해준 다음 r값을 빼줍니다.