[baekjoon] 두 수의 합 3273 (Javascript, c++)

Cafe Mocha 2022. 6. 14. 19:24

3273번: 두 수의 합

n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는

www.acmicpc.net

접근 방법

알고리즘 : 투포인터, 배열

1. n의 최대값이 100000으로 O(n^2)으로는 시간초과 발생

2. Javascript로는 투포인터 c++은 배열을 활용하여 풀이

Javascript

/**
 * 제출용. 아래 로컬용을 지우고 제출하자.
 */
//  let input = require("fs").readFileSync("/dev/stdin").toString().trim().split("\n")
/**
 * 로컬용, 예제.txt를 생성해서 예제를 복붙하자.
 */

function solution() {
  let input = require("fs")
    .readFileSync("input.txt") //"/dev/stdin"
    .toString()
    .trim()
    .split("\n")
    .map((val) => val.trim());

  let n = +input.splice(0, 1)[0];
  let arr = input[0].split(" ").map((v) => +v);
  let x = +input[1];

  arr.sort((a, b) => a - b);
  let cnt = 0;

  let i = 0;
  let j = n - 1;
  while (i < j) {
    if (arr[i] + arr[j] === x) {
      i++;
      cnt++;
    } else if (arr[i] + arr[j] > x) {
      j--;
    } else {
      i++;
    }
  }

  console.log(cnt);
}
solution();

C++

#include <bits/stdc++.h>
using namespace std;

int main()
{
  freopen("input.txt", "r", stdin); //제출 시 삭제

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

  int n,x;
  cin>>n;
  int arr[n];
  bool occur[2000001];

  for(int i=0;i<n;i++) {
    cin>>arr[i];
  }


  cin>>x;

  int cnt =0;

  for(int i=0;i<n;i++){
    if(x-arr[i]>0 && occur[x-arr[i]]) cnt++;
    occur[arr[i]]= true;
  }

  cout<<cnt<<"\n";


}