[프로그래머스,Java] Level3: 억억단을 외우자

 

문제분석

 

오랜만에 레벨 3 문제를 풀어보았다.

 

 

문제를 요약해보자면

1.적당한수 e 가 주어지고,   e보다 작은 여러개의 start지점이 주어집니다.

2.서로다른 start지점에서 e부터 최대 출몰하는 숫자를 입력합니다.

3. 최대 출몰하는 숫자가 여러개라면 작은숫자를 우선

 

 

First Try:  

1.먼저, 최대 출몰하는 숫자를 알려면,   그 숫자가 몇번 출몰하려는지 알아야 합니다.

 

억억단에서 그 숫자가 출몰하는횟수는  약수의 갯수 라는걸 알았고,  약수의 갯수를구합니다.

 

 

2.약수의 갯수를 구하여 약수 배열에 저장합니다.  매번 그 약수를 다시 구하는건 비효율적이니 dp 방식처럼

배열에 저장을 해놓았습니다.

 

약수의 갯수를 구하는 로직이 여러개 있지만,  해당문제는 여러개의 약수를 동시에 구해야하기때문에

다음 로직을 사용하엿습니다.

 

 

 

3.이 약수의 갯수를 구하는 로직을 구했으니, 2차반복문을 시행했습니다.

 

1차 : 모든 start지점

2차: start~ e 까지 

 

4. 2차반복문에서  최대 출몰하는 숫자가 여러개라면 작은숫자를 우선하는 조건문을 넣습니다.

 

 

 

--->>>  결론: 테케 9,10번 효율성 에러

 

만든 로직은 80점짜리 정답이었습니다. 

 

 

Second Try:

 

다른 사람의 풀이를 참고하였습니다.  참고를 하였더니, 확실히 효율적이라 감탄했습니다.

 

 

효율성 에러가 나는 부분은  First Try에서 3번째 부분 2차 반복을 시킨점에서 효율성에러

2차반복문을 더욱 줄여야 했다.  확실히 여기서 무분별한 탐색이 있었다.

 

해당 로직을 효율성으로 줄이려면  e 부터 1까지 최대 약수의 수를 가진 수를 갱신 및 저장하여 s의 위치를 배열에서 찾아내면 됩니다.

 

오름차순으로 해도 되지만, 내림차순으로 로직을 짜는게 더  짧은 코드가 만들어집니다.

이유는  출몰하는 숫자가 여러개있으면  "작은 숫자를 우선" 하기때문입니다.

 

로직은 다음과 같습니다.

이 로직은, 약수의 배열을 -> start~ e까지 탐색해서 최다 출몰하는 숫자배열로 바뀝니다.

 

이 로직을 거치고,  answer[i]에 담아주면 완성입니다.

 

 

문제풀이

class Solution {
    public int[] solution(int e, int[] starts) {
        
        int[] answer = new int[starts.length];
        
        //약수를 구하는 배열
        int[] dic = new int[5000001];
        
       for(int i = 1 ; i<=e ; i++){
            for(int j = 1 ; j<=(e/i) ; j++){
                dic[i*j]++;
            }
        }
        
        //max= 가장많이 출몰하는 숫자
        //maxaddr= 가장많이 출몰하는 숫자중 가장 적은 idx
        int max = 0, minaddr = 0;
 
        for(int j = e ; j >=0 ; j--){
            //maxaddr갱신 
            minaddr = max>dic[j]?minaddr:j;
            //max 갱신
            max = max>dic[j]?max:dic[j];
            dic[j] = minaddr;
        }
 
 
        for(int i = 0 ; i < starts.length ; i++){
 
            answer[i] = dic[starts[i]];
 
        }
        
        
        return answer;
    }
    
 
}