🔴 문제
🟡 Sol
const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'Wiki\\input.txt';
const input = fs.readFileSync(path).toString().trim().split('\n');
const n = Number(input[0]);
const seq = input[1]
.split(' ')
.map((it) => Number(it))
.sort((a, b) => a - b);
const x = Number(input[2]);
let cnt = 0;
let left = 0;
let right = n - 1;
while (left < right) {
const sum = seq[left] + seq[right];
if (sum === x) {
cnt += 1;
left += 1;
} else if (sum < x) {
left += 1;
} else {
right -= 1;
}
}
console.log(cnt);
🟢 풀이
const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'Wiki\\input.txt';
const input = fs.readFileSync(path).toString().trim().split('\n');
const n = Number(input[0]);
const seq = input[1]
.split(' ')
.map((it) => Number(it))
.sort((a, b) => a - b);
const x = Number(input[2]);
let result = 0;
while (seq.length > 1) {
const target = seq.pop();
for (let i = 0; i < seq.length - 1; i++) {
if (seq[i] + target === x) result += 1;
}
}
console.log(result);처음에 그냥 머릿속에 그려지는대로 위처럼 브루트포스를 사용해 모든 경우의 수를 따져줬더니 시간 초과가 발생했다.
이 문제의 시간 제한은 1초 였고, n과 x의 범위는 (1 ≤ n ≤ 100000, 1 ≤ x ≤ 2000000 였다.
내 코드는 while문에서 n, 내부의 for문에서 n 총 O(n2) 의 시간복잡도로 작성되었다.
✔ 시간 제한이 1초일때
N의 범위가 500인 경우 : 시간 복잡도가 O(N^3)인 알고리즘 설계
N의 범위가 2,000인 경우 : 시간 복잡도가 O(N^2)인 알고리즘 설계
N의 범위가 100,000인 경우 : 시간 복잡도가 O(NlogN)인 알고리즘 설계
N의 범위가 10,000,000인 경우 : 시간 복잡도가 O(N)인 알고리즘 설계
예전에 정리한 복잡도 내용 일부인데, 시간제한이 1초일때는 N의 범위에 따라 다음과 같은 알고리즘을 설계해야 한다. 즉 내 코드는 O(N) 의 알고리즘을 설계해야 됐던것이다.
따라서 O(n2) 의 O(N) 로 바꾸어주는 투 포인터 라는 알고리즘을 사용한다.
수열 seq의 가장 첫 값과 마지막 값에 각각 left와 right라는 포인터를 설정해둔 뒤 left가 right랑 같아질때까지 반복한다.
두 개의 값이 목표값보다 큰지, 작은지에 따라 포인터를 옮겨줘야 하기 때문에 seq배열은 정렬되어 있어야 한다는점!
left와 right를 위치의 요소를 더해 두 수의 합을 구하고 그 값이 목표값인 x와 같으면 정답 개수 cnt를 1증가시킨다. left값도 1증가시켜 다음 두 수의 값을 찾는다.
만약 두 수의 합이 목표값 보다 작다면 left값을 1증가시켜 sum값이 증가할 수 있도록 하고
두 수의 합이 목표값보다 크다면 right값을 1감소시켜 sum값이 감소할 수 있도록 한다.
반복을 마친뒤 cnt값을 출력하면된다.
🔵 Ref
