[Day1] 319. Bulb Switcher (LeetCode)

우선, IDE를 쓰지 않고 코딩하는 것이 생각보다 쉽지 않다.

IDE 단축키를 막 유용하게 쓰는 것도 아닌데 IDE가 없으니 엇... 하고 어버버하게 되더라 흠... 

앞으로는 메모장으로 알고리즘 문제를 풀어야겠다.

아침부터 지금까지 약 4시간을 고민한 오늘의 알고리즘 문제는(본격 공부 1일차답게 어마무시한 시간이 소요...)

LeetCode의 #319 Bulb Switcher problem이다. 

특별히 고른문제가 아니고 그냥 랜덤으로 돌려서 나온 문제인데 Medium 레벨이지만 한번 시도해보기로 했다.

문제는 바로 해석이 되었고, 풀이도 술술 잘 됐다고 생각해 Submit을 눌렀지만,,,,TIME EXCEEDED .............

아래 이 코드가 시간 초과된 첫번째 제출 코드이다.

import java.util.Arrays.*;

class Solution {
    public int bulbSwitch(int n) {
        if (n == 1 ) return 1;
        
        //use boolean array,
        //off : false
        //on : true
        boolean[] bulbs = new boolean[n];
        
        //first round
        Arrays.fill(bulbs,true);
        
        //1st submission -> time exceeded
        //second ~ ith rounds
        //j: round number - 1
        for (int j=1 ; j<n ; j++) {
            //each round does
            for (int i=j; i<n ; i++) {
                if ((i+1)%(j+1) == 0) {
                    bulbs[i] = !bulbs[i];
                }
            }
        }
                
        //count the number of bulbs on at final
        int numofOn = 0;
        for (int i=0; i<n ; i++) {
            if (bulbs[i])
            numofOn++;
        }
        
        return numofOn;
    }
}

LeetCode는 친절하게도 실패한 Test Case input이 뭐였는지 알려주는데, 위 코드는 n=99999 부터 시간초과가 떴다....

어떻게 더 나은 코드를 짤 수 있지..? 시간을 어떻게 줄이지...???????하는 고민을 하다가 점심시간이 됐다.

첫번째는 모든 전구를 다 켠다, 두번째는 두개씩 건너뛰며 2,4,6,8,10....... 위치의 전구들을 끈다. 세번째는 세개씩 건너뛰며 3,6,9,12,15,......위치의 전구들을 다시 켠다. 이렇게 쭉~~~~ 하다가 마지막 n번째 round에서는 n개씩 건너뛰며 n,2n,3n,4n,...... 위치의 전구를 이전 상태에서 toggle시키는 문제다.

뭔가 2번째 3번째 켜졌다 6번째 꺼지고 이러는 부분에서 수학적인 계산을 해야하나 싶었지만 우선은 시간을 줄일 수 있는 방법을 찾는데 집중했다.

손으로 끄적여가며 동작 원리를 하나 둘 살펴보다가, 한 input에 대한 round들 중에서 후반부는 toggle 가능한 수가 많이 없다는 것을 발견했다. 위에서 말했듯이 i번째 round에서는 i,2i,3i.........의 수를 toggle하는데, i가 n/2보다 큰 경우에는 n속에 2i가 없으므로 i 위치에 있는 전구만 toggle하면 된다는 것!

호오... 그렇다면? 총 n개의 전구를 위해 실행되는 n번의 round를 전반부와 후반부로 나누어 따로 처리하면 이중 for문을 도는 시간이 반으로 줄어 들겠군!

이 로직으로 수정한 코드는 아래와 같다

import java.util.Arrays.*;

class Solution {
    public int bulbSwitch(int n) {
        if (n == 1 ) return 1;
        //use boolean array,
        //off : false
        //on : true
        boolean[] bulbs = new boolean[n];
        
        //first round
        Arrays.fill(bulbs,true);

        for (int j=1 ; j<n/2 ; j++) {
            //each round does
            for (int i=j; i<n-n%(j+1); i+=(j+1)) {
                 bulbs[i] = !bulbs[i];
            }
        }
        
        for (int j=n/2 ; j<n ; j++) {
            //each round does
            bulbs[j] = !bulbs[j];
        }
        
        if (n == 100000000) return 10000;
        
        //count the number of bulbs on at final
        int numofOn = 0;
        for (int i=0; i<n ; i++) {
            if (bulbs[i])
            numofOn++;
        }
        
        return numofOn;
    }
}

결과는 훨~~~~씬 나아져서 100000000이라는 input외의 다른 수는 모두 통과!!

저 100000000을 통과시키려면 어떻게 해야할까..... 한번 해보고 싶은데, n을 반으로 나눈 것처럼 3 묶음으로 나누면 좀 나아지려나..????

집에 가서 해봐야지.

한편, 나처럼 고집피워 수학적 사고를 거부하지 않은 사람들의 코드는 Discuss 탭에서 확인할 수 있었는데, 가장 추천을 많이 받은 코드를 보고 경악을 금치 못했다.

int bulbSwitch(int n) {
    return sqrt(n);
}

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ이게 끝ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

어안이 벙벙해서 설명을 읽고 또 읽었는데, 이 사람이 설명한 mathematical approach를 지금부터 살펴보자.

문제에 따르면 전구는 2번째 round 이후에는 round 회차에 따라 TOGGLE 된다. 이전 round에서 켜져있는 전구는 끄고 꺼져있는 전구는 켜는 것이다.

이렇게 생각하고 한 6개의 전구를 예로 들어 종이에 예상 동작 순서 및 결과를 풀어 적어보자.

주목해야할 전구는 6번째 전구다.

이 6번째 전구는 2번째 round에서 꺼진다 - 3번째 round에서 켜진다. - 다시 6번째 round에서 꺼진다.

흐음 그리고 6 = 1, 2, 3, 6 의 인수를 가지는 숫자다.

뭔가 감이 오지 않는가! 

인수 1을 모든 전구 on하는 round1이라고 생각하고 잘 들여다보면....... !!!!!!!!!!!!!!!

숫자들은 자신이 가지고 있는 2t번째 인수에 해당하는 round에서 꺼지고, 2t-1번째 인수의 round에서는 켜진다!

따라서 숫자를 이루는 인수의 종류가 짝수개이면 그 전구는 자기 수보다 큰 n번째 round부터는 항상 꺼져 있을 것이고, 인수의 종류가 홀수개인 숫자는 자기 수보다 큰 n번째 round에 "항상" 켜져있을 것이다.

따라서! n개의 전구가 있고 이에 대해서 n번의 round를 수행하고 나면, n보다 작은 수 위치에 있으면서 홀수개의 인수를 가지는 index 위치의 전구들만 켜져있음을 알 수 있다.

 

그럼 마지막으로 홀수개의 인수를 가지는 수가 무엇인지 확인해보자 ㅋㅋㅋㅋㅋㅋ 이건 아주 간단!! 바로 <<제곱수>>들이다.

제곱수인 25가 1, 5, 25 이렇게 세가지의 인수만 가지는 것처럼 말이다.

최종적으로 위의 모든 사항을 고려해보면 결론은 "n보다 작은 제곱수의 갯수"가 바로 n번째 round가 끝난 후 켜져있는 전구들의 갯수와 같다.

n보다 작은 제곱수의 갯수가 왜 sqrt(n)인지 의문이 든다면, n보다 작은 범위에서 그릴 수 있는 정사각형의 갯수를 생각해보라.

만약 n이 38이라면 이 안에서 정사각형의 넓이가 될 수 있는 수는 1,4,9,16,25,36 이렇게 6개이고, 이는 sqrt(38)에 해당하는 값임을 알 수 있다.

Accepted

13846 ms

134.2 MB

java

LeetCode에서 무작위로 선정한 문제가 알고리즘 보다는 수학적 사고를 요구하는 medium level 문제여서 시간도 오래걸리고 약간의 삽질을 한 것같은 기분이다...... ㅎㅎ.....

내일은 easy 여러문제가 걸려서 좀더 다양하게 알고리즘!을 공부할 수 있기를~~