TIL 230526 : 구현은 끝이 아닌 새로운 시작.

프로그래머스에서 예전에 두려워했던 스킬체크 입문자를 도전해봤다.

쪼렙부터 마스터까지

두 문제로 40분이 주어졌다.

각 문제는 반복문과 배열의 기본, String클래스를 조금만 다루면 가능한 정도의 입문자용 난이도라는 게 느껴졌다.

 

40분이 넉넉하다고 생각했는데, 하다보니 생각보다 촉박했고 40분 전체를 알차게 다 쓰고 결과는 결국..

 

83.3점으로 탈락이었다.

 

당황스러웠던 것은 Lv.0을 풀면서 코드가 실행되게끔, 그리고 실행된 코드가 맞는 결과값이 나오게 하는것이 모든 과제였는데 채점결과가 당황스러웠다.

시간초과라는 경우의 수는 그동안 없었던터라 상당히 어안이 벙벙했다.

코드가 실행이 안되는 것처럼 문법이 틀린 것도 아니고, 결과가 틀린 것도 아닌데 시간초과로 실패라니.

 

약수를 모두 구해라

시간초과가 나오게 된 포인트였다. 분명 구현은 문제없이 해냈다.

'2중 for문? 2중 if문은 쓰레기다.'라는 말을 들은 기억이 있었는데 아무렴.. 다른 방법이 없어서 우선 구현했다.

 

문제는 예제 입력데이터값이 100,000이 넘어가는게 있었다. 이 경우에 숫자 1부터 100,000까지 모두 나머지 값이 0인 값을 찾는 반복문을 돌려서 이때 시간이 많이 초과된듯하다.

 

---

2중 for문이 문제였나??

 

시험 시간 40분동안에 처음해보는 고민을 했다.

'응답시간을 줄이려면 어떻게 해야하지?' 뇌의 어떤 부분이 처음 사용되는 기분이었고, 당연히 남은 4분동안 별다른 소득없이 시험을 마쳤다.

 

for(int i = 1; i<array.length+1; i++){
	for(int j=1; j<=i; j++){
    	if(i%j==0){
        	array[i-1]++;
        }
    }   
}

 

약수를 구하는 파트를 돌이켜보면 대략 위와 같았다.

1. 1부터 특정 숫자까지 각 숫자의 약수의 개수를 구해야했다.

2. 모든숫자를 우선 확인해야했고, 각 숫자에 1부터 그 숫자까지 나누기를 해봐서 나머지가 0인 수들을 카운트 해줘서 배열에 넣었다.

 

2중for문이 문제였나?? 하지만 특정숫자를 건너뛰고 약수를 구할 수는 없었다.

다른 사람들의 코드를 보니 예를들어 12의 모든 약수를 구하기 위해 1부터 12까지 나눴을때의 나머지를 다 구할필요가 없었다.

12의 반절인 6까지만 약수를 구했다면 그 이후부턴 지금 까지 구한 약수와 짝을 이루는 수라서 자동으로 두배정도가 된다.

 

 모든 자연수는 1을 약수로 가진다.

 모든 자연수는 자기 자신을 약수로 가진다.

 

여기서 한번더 생각해보면

 모든 자연수는 1을 약수로 가진다.

  -> 1보다 큰 존재할 수 있는 가장 작은 약수는 2이다.

 모든 자연수는 자기 자신을 약수로 가진다.

  -> 자기 자신보다 작은 약수 중 가장큰 건 자기 자신의 반절이다.

 

12로 예를 들자면, 12의 약수 중에 자기자신인 12는 당연히 있고, 그 다음으로 큰 약수는 6인 것이다.

 

다시말해 100,000의 약수중 100,000다음으로 가장 큰 약수는 50,000인 것이다.

위의 코드에 따르면 나는 

 

if(100,000%50,001 == 0)

if(100,000%50,002 == 0)

...

if(100,000%99,999 == 0)

위의 if식이 굳이 발동된 것이다.

 

더 나아가서, 1부터 약수를 구하다 일정 분기 이상부터는 기존의 나온 약수와 쌍을 이루는 약수들이다.

일정분기란 제곱근이 될테고, 12의 예로 따져보자.

 

1, 2, 3, 4, 6, 12 이렇게이다.

쌍으로 지어본다라는 의미는

1 * 12

2 * 6

3 * 4

 

3까지만 구하면 사실상 그때까지의 약수의 개수의 2배가 전체 약수의 개수라는 뜻이다.

3까지만이라는 기준이 엄밀히 따지면 제곱근이다. 두 항이 똑같은 수의 곱이니까 앞 뒤 숫자가 정확히 같은 포인트이니.

 

12의 제곱근인 3.464.. 즉 3까지만 약수 테스트를 해보면 됐던 것이다.

 

여기에 제곱근 자체가 약수인 경우, 예를들어 16은 4*4가 존재하는데 이는 중복이라 4까지의 약수를 구해준 뒤 2배를 해주고 중복값 1만 빼주면 약수의 개수를 구하는 시간을 줄일 수 있었다.

 

정수론에 관련된 개념이긴하지만 조금만 생각해봐도 굳이 일정 숫자의 반을 초과하는 숫자에 대해서는 연산할 필요가 없었는데 하는 생각이 든다.

 

이를 활용하여 풀은 코드를 참고하며 마친다..

import java.util.*;

class Solution {
    public int solution(int number, int limit, int power) {
        int answer = 0;
        
        for (int i=1; i<=number; i++) {
            int n = getCommonFactor(i);
            int iron = 0;
            iron = n > limit ? power : n;
            answer += iron;
        }
        
        return answer;
    }
    
        public int getCommonFactor(int n) {
        int count = 0;
        for (int i = 1; i <= Math.sqrt(n); i++) {
            if (n % i == 0) {
                count = Math.pow(i, 2) == n ? ret+1 : ret+2;
            }
        }
        return count;
    }
}

 

 

---

구현이 다가 아니었다.

마침 오늘 예외처리에 대해 배웠는데, 강사님이 하신 말씀 중 하나가 꽂혔다.

초보때는 구현에 집중해요. 어떻게든 구현을 시키는 게 과제니까. 그런데 이제는 예외처리나 이런 다른 것들에도 신경을 더 써야해요.

또 하나로는 유튜브에서 비전공자를 위한 첫걸음에 대한 콘텐츠를 찾아서 보다가 '소프트웨어 디자인 패턴'에 대해서도 언급해줬다.

예전에 듣기는 했었던 싱글톤 패턴.. 무슨 패턴.. 초보시절때 궁금해서 보다가 포기한 설명콘텐츠를 다시보니 이제 조금은 알듯하다.

Static 영역에서의~~  객체를 하나만 써야하는 경우엔~~ 등등 그저 구현이 다가 아니라 상황에 맞는 코딩을 구현하는 것에 초첨이 맞춰진듯하다.

 

게임으로 치면 튜토리얼 지역을 거의 끝내갈때쯤 '다른 새로운 것들이 더 있으려나?'하던 찰나에 더 넓은 전체지도를 본것 같은 느낌이다.

 

내가 모르는게 뭔지 모르는 상황에서, 이러이러한 부분들을 모르고 있다 정도로를 깨달은 것 같은 날이다. 기분이 묘하게 좋다. 모르는게 많이 생겼다.