[프로그래머스 C#] Lv.3 억억단을 외우자

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

프로그래머스

1. 정답코드 및 핵심 아이디어, 유의사항

주어진 조건에 따른 퀴즈의 답 목록을 구하는 문제

- 퀴즈 : 주어진 숫자 ~ e까지의 범위의 수 중에 억억단에 등장한 횟수가 가장 많은 최소 값

 

풀이 순서

- 1부터 e까지의 범위안에서 억억단에 등장한 횟수를 기록 (countArray) 

- dp배열에 dp배열의 인덱스번호 ~ e까지의 억억단 등장 횟수 중에 가장 많이 등장한 최소 값을 저장

 -> 퀴즈에서 변하지 않는 기준이 e이므로 역순으로 dp 배열 세팅을 진행

 -> 즉, dp배열의 인덱스 번호에 최종적으로 담기는 값이 퀴즈의 정답이 됨

 

DP 알고리즘 ( 동적 계획법 )

https://godgjwnsgur7.tistory.com/109

[Algorithm C#] 동적 계획법(DP) / Memoization, Tabulation

주석 참조

    using System;

    public class Solution
    {
        public int[] solution(int e, int[] starts)
        {
            int[] answer = new int[starts.Length];
            var countArray = new int[e + 1]; // 해당 인덱스의 숫자가 등장한 횟수를 담을 배열
            var dp = new int[e + 1]; // index ~ e범위의 가장 많이 등장한 최소 값

            // countArray 세팅 (억억단 등장 횟수)
            for (int i = 1; i <= e; i++)
            {
                for (int j = 1; j <= e; j++)
                {
                    if (i * j > e)
                        break;

                    countArray[i * j]++;
                }
            }

            // dp 세팅 (i ~ e 범위)
            int maxCount = -1;
            int index = -1;
            // 변하지 않는 기준이 e이므로 역순으로 진행
            for (int i = dp.Length - 1; i >= 0; i--)
            {
                if (maxCount <= countArray[i])
                {
                    maxCount = countArray[i];
                    index = i;
                }

                dp[i] = index;
            }

            // 퀴즈 답 목록 세팅
            for (int i = 0; i < starts.Length; i++)
                answer[i] = dp[starts[i]];

            return answer;
        }
    }