319. Bulb Switcher (Math)

<문제 풀이 과정>

단순 반복문을 사용한 구현 풀이 -> Time Out

class Solution {
    public int bulbSwitchFail(int n) {
        if(n==0) return 0;
        int ans = 0;
        boolean[] array = new boolean[n+1];
        Arrays.fill(array,false);
        for (int i = 1; i < n; i++) {
            for (int j = i; j <= n; j+=i) {
                array[j] = !array[j];
            }
        }
        array[n] = !array[n];

        for (boolean unit: array)
            if(unit) ans++;

        return ans;
    }
}

단순 반복문으로는 해당 문제를 해결할 수 없기 때문에 수학적으로 접근해야 했다.

해당 반복을 자세히 보면 각 n번째 전구는 n의 약수 일 때만 상태가 바뀜을 알 수 가 있다.

즉 6번 전구의 경우에는: Round가 1, 2, 3, 6일 때 마다 바뀌게 된다.

 

전구(n)가 불이 켜진 상태가 되려면 짝수번 바뀌어야 하고 (n의 약수의 갯수가 짝수)

불이 꺼진 상태가 되려면 홀수번 바뀌어야 함을 알 수 있다. (n의 약수의 갯수가 홀수)

 

즉 1~n까지의 경우에서 답은 

해당 숫자(n)에서 약수의 갯수가 홀수인 수의 갯수 임을 추론 할 수 있다.

 

약수의 갯수가 홀수가 나오기 위해서는 완전 제곱수가 되어야 한다.
ex: 4 -> 1,2,4  9 -> 1,3,9  16 -> 1,4,16

 

즉 해당 문제는 1~n까지의 수중에서 완전 제곱수의 갯수를 구하는 문제임을 
알 수 있다. 

 

<풀이 코드>

class Solution {
    public int bulbSwitch(int n){
        int ans = 0;
        for (int i = 1; i*i <= n; i++) {
            ans++;
        }
        return ans;
    }
}

이런 식으로 반복문으로 답을 구할 수도 있지만

 

좀 더 간결하게 바꾼다면
수학적 정의의 의하면 n의 제곱근은 1~n까지의 자연수 중에서 완전 제곱수의 갯수와
동일함을 이용한다면

 

<최종 정답 코드>

class Solution {
    public int bulbSwitchOtimal(int n){
        return (int)Math.sqrt(n);
    }
}

다음과 같이 아주 간결하게 줄일 수가 있다.