23.04.27. 풀었던 문제들

Leetcode 319. Bulb Switcher

 오늘 풀었던 문제는 좀 레전드인 것 같다.

 

 이 문제는 어떤 수 i의 약수 개수를 쉽게 풀 수 있다면 쉽게 풀 수 있는 것으로 보인다. i의 약수 개수만큼 bulb가 꺼졌다 켜졌다 하기 때문이며, 결과적으로 i의 약수 개수가 홀수면 켜져 있는 상태가 될 것이다. 따라서 1 <= x <= n에 대해 약수 개수가 홀수인 수의 개수를 리턴하면 되는 문제이다.

 

 그런데.. 소수 판정 증명 포스트에서 "자연수 n에 대해 n의 어떤 약수 x와 n/x에 대해 min(x, n/x) <= $sqrt(n)$이다"를 증명했다. 여기서 하나의 아이디어를 알 수 있는데... 자연수 n에 대해 n의 어떤 약수 x와 n/x는 pair를 이루고 있다는 것을 알 수 있다. 즉슨... 예를 들어

• 6은 1, 2, 3, 6으로 4개
• 7은 1, 7로 2개
• 8은 1, 2, 4, 8로 2개
• 9는 1, 3, 9로 3개

이다. 단, 제곱수 제외. 제곱수는 x와 n/x가 pair를 이룰 때, x과 n/x가 같기 때문에 pair를 이루지 않는다. 다른 모든 수는 pair를 이룬다. 따라서 n보다 작은 제곱수의 개수가 정답이 될 것이다.

class Solution {
public:
    int bulbSwitch(int n) {
        return sqrt(n);
    }
};

 

시간복잡도 & 공간복잡도

 별다른 공간 사용하지 않는다. O(1)