알고리즘 직각 삼각형 3000번 (Node.js)

제 방법이 최고인 것도 아닐테지만,  그냥 node에서 저만 맞춘게 기분이 너무 좋아서 올려봅니다.

문제

좌표 평면에 점 N개가 있다.

이때, 빗변을 제외한 나머지 두 변이 좌표축에 평행한 직각삼각형을 이루는 점 3개를 고르는 방법을 수를 구하는 프로그램을 작성하시오.

직각삼각형은 한각이 직각인 삼각형이며, 직각의 대변을 빗변이라고 한다.

 

 

입력

 

첫째 줄에 점의 개수 N(3 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 점의 좌표가 X Y 순서대로 주어진다. (1 ≤ X,Y ≤ 100,000) 겹치는 점은 없다.

출력

첫째 줄에 직각삼각형의 개수를 출력한다.

예시

풀이 

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

const n = +input[0];
const array = [];
const yCount = new Array(100001).fill(0);
for (let i = 1; i <= n; i++) {
  const [x, y] = input[i].split(' ').map(Number);
  if (array[x] === undefined) {
    array[x] = [y];
    yCount[y]++;
  } else {
    array[x].push(y);
    yCount[y]++;
  }
}

let result = 0;
for (let i = 1; i < array.length; i++) {
  if (array[i] && array[i].length > 1) {
    for (let j = 0; j < array[i].length; j++) {
      result += (yCount[array[i][j]] - 1) * (array[i].length - 1);
    }
  }
}
console.log(result);

생각 : 우선 배열 안에다 x,y축에 대한 정보를 담습니다.

그리고 x축이 같은 값 2개를 선정하고, 각각의 점에 대해서 y축값은 같은데 x축이 다른 점의 개수를 세어주면 됩니다.

그러기 위해선 우선 배열안에 x축에 대한 y값을 담습니다.

이후 yCount라는 배열을 통해서  y축 같은 x의 값의 개수를 세어줍니다.

조건에서 값이 100000만 이하이기 떄문에 yCount는 100001 까지 초기값을0 으로 만들어 줍니다.

 

이후 들어온 input값에 대해서 yCount를 증가시키고, array배열안에 해당 x축에 대한 y값을 넣어줍니다.

위 input예시에 대한 정리된 값은 아래와 같네요

 

 

let result = 0;
for (let i = 1; i < array.length; i++) {
  if (array[i] && array[i].length > 1) {
    for (let j = 0; j < array[i].length; j++) {
      result += (yCount[array[i][j]] - 1) * (array[i].length - 1);
    }
  }
}

이후  for 문을 통해서 순회를 하는데 yCount에는 자기자신이 포함되니 -1, 그리고 각각의 값을 x축에 본인이 아닌 값이 있는 횟수만큼 더해지기 때문에 array[i].length-1

빨간점을 기준으로  잡앗을 때(10,10)와 (10,20), 1 +2 가  (20,10)  +   (20,20) , (30,20)이 더 해지는데 

이는 10,10에 대해서 y 값이 같은 (10) 인 값들 중 본인이 아닌 값을 더 한 거고

이는 만약 x축이 같으면서 y축이 다른 값이 여러개 존재하게 되면, 해당 값들이 더 해주는 횟수가 x축이 같으면서 y축이 다른 값들의 갯수 만큼 증가하기 때문이다.

 

for (let i = 1; i < array.length; i++) {
  if (array[i] && array[i].length > 1) {
    for (let j = 0; j < array[i].length; j++) {
      for (let k = j + 1; k < array[i].length; k++) {
        result += yCount[array[i][j]] - 1;
        result += yCount[array[i][k]] - 1;
      }
    }
  }
}

이 전에 시간초과가 났떤 이유를 위와 같은 로직이 아닌 반복문 한 개를 더 해서 일일이 다 더해줬기 떄문입니다.

유독 그래프에 대한 문제가 없어서, 한 개 풀었는데 성장하는 기분이라 좋네요, ㅎㅎ,,,,