[백준/완전탐색] 5618번. 공약수(JavaScript)

문제

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

 

풀이

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

const n = parseInt(input.shift(), 10);
const data = input.toString().split(' ').map(Number);
data.sort((a, b) => a - b);

let result = [];

function solution(n, data) {
    let arrays = [];
    for (let i = 0; i < n; i++) {
        let array = new Array();
        for (let j = 1; j <= data[i]; j++) { // 각각 수의 공약수를 구함
            if (data[i] % j == 0) {
                array.push(j);
            }
        }
        arrays.push(array);
    }
    result = arrays[0];
    for (let i = 0; i < arrays.length - 1; i++) {
        let temp = arrays[i].filter((it) => arrays[i + 1].includes(it)); // 두 배열에 공통으로 있는 것을 temp에 담음
        result = result.filter((el) => temp.includes(el)); // temp에 있는 것으로 result를 다시 필터링함
    }
}

solution(n, data);
result.forEach((el) => console.log(el));

 

내 풀이는 위와 같았다.

시간복잡도를 계산하는 연습을 하고 있어서, 내 코드의 시간복잡도를 계산해봤는데,

1초에 10^8번 계산이 가능하면 문제에서 자연수가 10^8 이하라고 하였으므로 최악에는 n이 3이고 자연수가 10^8일 때 3x10^8번을 하게 되어, 3초가 필요하게 될 것이라고 생각했었다.

그치만 문제의 제한시간은 1초였고, 통과해서 왜 통과했을지 궁금해 멘토님께 여쭤봤다.

이번 문제의 경우 for문안의 로직이 간단해서 가능했던 것 같다는 의견을 들었다. c++기준으로는 0.7초가 나왔다고 했다.

 

또 filter(), includes()와 같은 자바스크립트 배열 메소드는 배열 처음원소부터 찾는 거라 O(n)이 걸린다고 알고 있는데,

filter와 includes()를 동시에 하면 O(n^2)이 걸린다.

arrays.length-1은 n이 2나 3 정도여서 1, 2가 되어 시간복잡도에 큰 영향을 주지 않는다.

그리고 1억을 기준으로 공약수의 개수는 80개 이기 때문에 n제곱이나 n의 세제곱이나 의미는 크게 없다고 한다.

 

더 열심히 풀어야겠다!!