[프로그래머스 Level.3] 억억단을 위우자 (연습문제) (Java)

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/138475

프로그래머스

 

 

 

코딩테스트 연습 > 연습문제 > 억억단을 위우자

 

 

 

문제 설명

 

 

영우는 천하제일 암산대회를 앞두고 있습니다. 암산보다는 암기에 일가견이 있는 영우는 구구단을 확장하여 억억단을 만들고 외워버리기로 하였습니다.

 

억억단은 1억 x 1억 크기의 행렬입니다. 억억단을 외우던 영우는 친구 수연에게 퀴즈를 내달라고 부탁하였습니다.

수연은 평범하게 문제를 내봐야 영우가 너무 쉽게 맞히기 때문에 좀 어렵게 퀴즈를 내보려고 합니다. 적당한 수 e를 먼저 정하여 알려주고 e 이하의 임의의 수 s를 여러 개 얘기합니다. 영우는 각 s에 대해서 s보다 크거나 같고 e 보다 작거나 같은 수 중에서 억억단에서 가장 많이 등장한 수를 답해야 합니다. 만약 가장 많이 등장한 수가 여러 개라면 그 중 가장 작은 수를 답해야 합니다.

수연은 영우가 정답을 말하는지 확인하기 위해 당신에게 프로그램 제작을 의뢰하였습니다. e와 s의 목록 starts가 매개변수로 주어질 때 각 퀴즈의 답 목록을 return 하도록 solution 함수를 완성해주세요.

 

---

제한사항

• 1 ≤ e ≤ 5,000,000
• 1 ≤ starts의 길이 ≤ min {e,100,000}
• 1 ≤ starts의 원소 ≤ e
• starts에는 중복되는 원소가 존재하지 않습니다.

 

---

 

입출력 예

e	starts	result
8	[1,3,7]	[6,6,8]

 

---

 

입출력 예 설명

 

억억단에서 1 ~ 8이 등장하는 횟수는 다음과 같습니다.

 

1번 등장 : 1
2번 등장 : 2, 3, 5, 7
3번 등장 : 4
4번 등장 : 6, 8

 

[1, 8] 범위에서는 6과 8이 각각 4번씩 등장하여 가장 많은데 6이 더 작은 수이므로 6이 정답입니다.
[3, 8] 범위에서도 위와 같으므로 6이 정답입니다.
[7, 8] 범위에서는 7은 2번, 8은 4번 등장하므로 8이 정답입니다.

 

 

 

 

나의 코드

class Solution {
    public int[] solution(int e, int[] starts) {
        int[] answer = new int[starts.length];
        int[] dp = new int[e+1];
        
        for(int i=1; i<=e; i++) {
            for (int j=1; j<=e/i; j++) {
                dp[i*j]++;
            }
        }
        
        int[] arr = new int[e+1]; // arr[i]는 i~e까지 dp[i] 큰 수의 i 저장(같다면 작은 i)
        arr[e] = e;
        int temp = dp[e];
        for(int i=e-1; i>=0; i--) {
            if(dp[i] >= temp) {
                arr[i] = i;
                temp = dp[i];
            } else {
                arr[i] = arr[i+1];
            }
            // System.out.println("arr["+i+"]="+arr[i]);
        }
        
        for(int i=0; i<starts.length; i++) {
            answer[i] = arr[starts[i]];
        }
        
        return answer;
    }
}

 

 

풀이

1. 임의의 수 e에 대해서 starts[i] 이상 e 이하인 수 중에 가장 많이 등장한 수 중에 가장 작은 수를 구하는 문제이다.
2. dp를 이용하여 푸는 문제로 우선 1~e까지 해당 숫자의 개수를 저장할 배열을 생성하여 저장한다.
3. 1~e까지의 개수만 구하면 되므로 int[] dp = new int[e+1] 로 생성한다.
4. dp[e]까지만 구하므로 이중for문을 통해 첫번째 for문은 i<=e까지 , 두번째 for문은 j<=e/i 까지로 조건식을 만든다.
5. 이렇게 1~e까지 개수를 저장한 dp 배열을 가지고 문제의 조건처럼 starts[i] 이상 e 이하인 수 중에서 가장 많이 등장한 수를 구하기 위해 arr 배열을 생성한다.
6. arr 배열은 i부터 e까지 dp[i]가 큰 수를 저장할 것이다. 그러면 i부터 e까지중에 가장 많이 등장한 수가 저장된다.
   물론 가장 많이 등장한 수가 같다면 작은 인덱스를 저장한다.
   (arr[srtarts[i]]는 dp[starts[i] ~ e] 까지 중에 가장 큰 수가 저장되어 있는 수의 인덱스를 저장한 배열)
7. e부터 시작하여 1까지 거꾸로 내려오면서 dp[i ~ e]의 큰 수를 arr[i]에 저장하면 된다.
   우선 arr[e]는 arr[e ~ e] 이므로 e가 저장된다.
   그리고 arr[e-1]부터 dp의 값을 비교해주기 위해 int형 변수 temp에 dp[e]를 저장한다.
   for문을 통해 arr[e-1 ~ e] 부터 시작하여 arr[1 ~ e] 까지 dp 배열과 temp를 이용하여 저장해 나간다.
8. 그리고 starts 배열을 for문을 돌면서 arr[starts[i]]에 해당하는 값을 가져와 answer에 저장하고 리턴한다.