[JS로 코테 준비하기] 6. 프로그래머스 - 순서쌍의 개수 (feat. 시간복잡도 제한)

https://school.programmers.co.kr/learn/courses/30/lessons/120836

프로그래머스

문제는 간단하다. 주어진 숫자의 약수의 개수를 구하는 것!
다만, JS의 시간복잡도 제한에 대한 고민이 드는 문제였다.

시간복잡도에 따른 입력의 크기

일반적으로 C++은 O(n)의 시간복잡도를 처리할 때, 입력의 크기를 1억으로 제한한다.
이를 넘어가면 시간초과가 나오도록 설계되어 있다.

Javascript의 입력 제한은?

위 문제를 통해 테스트해보자.

입력 제한은 1 <= n <= 1,000,000 였지만, 아래의 수를 테스트케이스에 추가했다.

n	return
1,000,000 (백만)	49
100,000,000 (1억)	81
1,000,000,000 (10억)	100
10,000,000,000 (100억)	121

 

1. O(n) 풀이

• 입력이 10억일 때까지 잘 돌아가다가, 100억에서 멈추고 시간초과가 나타나는 것을 확인할 수 있다.

function solution(n) {
      let cnt = 0;
      for(let i = 1; i<=n; i++){
          if(n % i == 0) cnt++;
      }
      return cnt;
  }

100억에서 시간초과

 

2. 범위를 더 좁혀보자

• 21억까지 실행되고, 22억에서 시간초과가 발생하는 것을 확인할 수 있다.

n	return
2,000,000,000 (20억)	110
2,100,000,000 (21억)	324
2,200,000,000 (22억)	180

22억에서 시간초과

 

3. 결론

• JS의 O(n) 시간복잡도의 입력 제한은 대략 21억이다.
• 21억이라는 숫자를 보니, C의 int 범위가 생각난다. (연관이 있을 것 같다는 뇌피셜을 돌려본다)
• 사실 JS로 알고리즘을 풀 때는 이미 구현되어 있는 내장 함수를 주로 활용하기 때문에 시간복잡도가 큰 영향을 미치지 않는다고 들었다. 그래도 혹시 모를 상황에 대비해 대충 입력 제한 범위를 알고있는 것은 좋은 것 같다.

추가) 그래도 시간복잡도는 중요

• 100억이 넘는 입력값도 받아들일 수 있도록 O(√n) 풀이를 지향하자.
• 약수와 관련된 풀이 자체는 https://gyyeom.tistory.com/51를 참고하자.

 

O(√n) 풀이

function solution(n) {
    let cnt = 0;
    for(let i = 1; i*i<n; i++){
        if(n % i == 0) cnt++;
    }
    return Number.isInteger(Math.sqrt(n)) ? cnt * 2 + 1 : cnt * 2;
}