3-8. [투포인터] 좋은 수 구하기

좋은 수

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

256 MB

18077

4483

3216

23.863%

문제

N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다.

N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라.

수의 위치가 다르면 값이 같아도 다른 수이다.

입력

첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수)

출력

좋은 수의 개수를 첫 번째 줄에 출력한다.

예제 입력 1 복사

10
1 2 3 4 5 6 7 8 9 10

예제 출력 1 복사

8

힌트

3,4,5,6,7,8,9,10은 좋다.

출처

• 데이터를 추가한 사람: BaaaaaaaaaaarkingDog, baggomsoon96, jame0313
• 문제의 오타를 찾은 사람: jh05013
• 빠진 조건을 찾은 사람: tongnamuu
• 문제를 만든 사람: xhark

---

풀이

1. 1부터 ~ 수의 개수 N까지의 순차적인 배열을 만든다.
2. 배열을 loop으로 하나씩 돌면서, 배열의 두 수를 더했을 때, 해당 element와 같을 때 break, count++
3. 다음 element로 이동 후 똑같이 실행

 

코드

const N = 10;
const list = [];
let count = 0;

for (let i = 1; i <= N; i++) {
  list.push(i);
}

for (let x = 0; x < list.length; x++) {
  const element = list[x];
  let i = 0;
  let j = N - 1;

  while (i < j) {
    const sum = list[i] + list[j];
    if (sum === element) {
      if (i !== element && i !== element) {
        count++;
        break;
      } else if (i === element) {
        i++;
      } else {
        j--;
      }
    } else if (sum < element) {
      i++;
    } else {
      j--;
    }
  }
}

console.log(count);