문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/138475
1억 x 1억 크기의 행렬이 존재하고,
그 정수 s~e 사이 범위에서 가장 많이 나오는 정수가 뭔지를 알아내는 문제
문제 핵심 및 풀이
제한 사항을 보면 1억 x 1억짜리 행렬은 아니더라도,
최댓값 e가 5,000,000까지 가능하기 때문에 O(n^2) 연산만 해도 바로 시간초과
그리고 O(N) 짜리 연산을 하더라도 모든 starts 값에 대해서 답을 구해준다면,
starts의 최대 길이는 100,000이니까, 10^5 * 10^6 이어서 역시 시간초과다.
결국 모든 starts의 범위에 대한 값을 미리 구해놓을 수밖에 없다.
즉, 메모라이징 기법을 이용하는 DP 문제라고 대놓고 말하고 있다.
다행히도 e는 하나이기 때문에, 끝 범위는 정해져있다.
그래서 2차원이 아닌 1차원 DP로 풀면 충분하다.
첫 번째 풀이
첫 번째 풀이는 어떻게 생각해 보면 숫자가 나오는 규칙성을 파악하는 것이다.
숫자 하나를 잡고 그 숫자가 어디서, 또 얼마나 나오는지를 확인해 보자.
여기서는 4와 6을 관찰해 보자.
이렇게 보면 한 가지 범위적인 특징을 알 수 있다.
바로 화살표로 그어놓은 범위,
그러니까 해당 수의 제곱수를 초과할 때가 되면 더 이상 그 수가 나오지 않는다.
이 말은 어떤 수의 개수를 구할 때 범위가 제한되어 있다는 것이다.
이는 최대 범위 e에도 적용되는 말이기 때문에,
결국 우린 최대 범위 e안에 있는 수의 개수만 다 구하면 된다는 소리이다.
모든 수에 대해서 번호와 나온 횟수를
저장하는 변수를 만들고 이를 저장한다.
for(int i = 2; i <= e; i++)
for(int j = 1; j <= e; j++) {
if(i * j > e) break;
dp[i*j].count++;
}그리고 각 행을 순차적으로 탐색하는데,
각 열에 적혀있는 번호에 해당하는 변수를 +1 한다.
행을 순차적으로 탐색하는 것은
해당 값이 e보다 커지면 다음 행으로 넘어간다.
이렇게 하면 모든 수에 대해 나온 횟수에 대해 알 수 있다.
위에 코드에서 2부터 해준 것은
1은 어차피 모든 수에 더해지기 때문에,
비교할 때는 없어도 상관없기 때문이다.
그리고 이를 횟수에 대해 내림차순 정렬하고,
횟수가 같을 때에는 번호에 따라 오름차순 정렬하면 된다.
이 방법이 보편적으로 푼 방법이고, 나도 이 방법으로 풀었다.
근데 이 방법이 웃긴 게,
C++로 풀었을 때는 간단하게 통과되는데, C#으로 풀었을 때는 시간초과가 난다.
겨우겨우 최적화를 조금 해서 9.5초로 통과했다.
이를 좀 더 개선할 방법이 없을까 해서
인터넷을 찾다가 두 번째 방법을 찾아냈다.
두 번째 풀이
두 번째 풀이는 좀 더 DP적이고 명료한 풀이다.
기본적으로 각 수가 나오는 횟수를 구하는 것은 위 방법과 같다.
다른 것은 밑의 방법이다.
위에서는 정렬하는 방법을 사용했다면, 여기서는 점화식 같은 방식을 사용한다.
dp [i] = i : i ~ e까지 탐색했을 때의 최대 개수를 가지는 번호
arr [i] = k : 수 i가 나온 횟수 k
여기서 1차원 점화식을 사용할 수 있는 이유는 끝 범위인 e가 고정이기 때문이다.
arr [i]는 위와 같은 방식으로 구한다.
그리고 e부터 역순으로 탐색하면서
해당 범위에서 가장 많은 개수가 나오는 번호를 저장한다,
역순으로 탐색하는 이유는 개수가 같다면
숫자가 작은 것을 담아야 하기 때문이다.
일단 모든 dp [i] = i로 초기화하여 자기 자신을 나타내도록 한다.
그리고 e가 8이라면 7부터 역순으로 1까지 탐색한다.
처음에는 dp [7]은 arr [7]과
기존의 dp [8]에 저장되어 있던 숫자를 비교한다.
dp [8] = 8 즉, arr [8] = 4이다. 그리고 arr [7]은 2이다.
즉 dp [7]은 그대로 8이 된다.
이런 식으로 1까지 가면 된다.
여기서 두 개수가 같다면 더 작은 수로 바꿔준다.
코드 구현
C++ 구현 코드
↓
1번 방식 풀이
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
// 정보를 담은 구조체를 선언
struct Point{
int num,count; // num -> 번호, count -> 나온 횟수
};
// 횟수에 따라 내림차순, 같다면 번호에 따른 오름차순
bool compare(Point a, Point b){
if(a.count == b.count) return a.num < b.num;
return a.count > b.count;
}
vector<int> solution(int e, vector<int> starts) {
vector<Point> dp(e+1);
// 각각 dp를 자기 자신으로 초기화하고 개수는 0
for(int i = 1; i <= e; i++) dp[i] = {i,0};
// 각 번호의 나온 횟수를 구하는 방식
for(int i = 2; i <= e; i++)
for(int j = 1; j <= e; j++) {
if(i*j > e) break;
dp[i*j].count++;
}
// 위 정렬 규칙에 따라 정렬
sort(dp.begin(),dp.end(),compare);
vector<int> answer;
for(auto it : starts){
int s = it;
// 앞에 있을수록 나온 횟수가 높은 것
// 앞에 있는 것이 횟수도 높은데 번호까지 s보다 크다면 그게 답
for(int i = 0; i <= e; i++){
if(dp[i].num >= s){
answer.push_back(dp[i].num);
break;
}
}
}
return answer;
}
C++은 위 방식으로 풀어도 테스트 10번까지 넉넉하게 통과한다.
2번 방식 풀이
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
vector<int> solution(int e, vector<int> starts) {
int minS = starts[0];
// 시간을 줄이기 위해 S중 최솟값을 찾아 넣음
for(auto it : starts) minS = min(minS,it);
vector<int> dp(e+1),arr(e+1); // arr, dp 배열 만듬
for(int i = 1; i <= e; i++) dp[i] = i;
// arr에 각 번호의 개수 채워넣음
for(int i = 2; i <= e; i++)
for(int j = 1; j <= e; j++) {
if(i*j > e) break;
arr[i*j]++;
}
// e-1개부터 역순으로 탐색
for(int i = e-1; i >= minS; i--){
if(arr[i] >= arr[dp[i+1]]) dp[i] = i;
else dp[i] = dp[i+1];
}
// 정답 채워넣기
vector<int> answer;
for(auto it : starts) answer.push_back(dp[it]);
return answer;
}
확실히 두 번째 방법으로 풀었을 때가 시간이 덜 걸린다.
↑
C# 구현 코드
↓
1번 방식 풀이
using System;
using System.Collections.Generic;
public class Solution
{
// 번호와 개수의 정보를 담은 클래스 정의
public class Info : IComparable<Info>
{
public int num { get; set; } // 번호
public int count { get; set; } // 개수
// 생성자
public Info(int num, int count)
{
this.num = num;
this.count = count;
}
// 정렬 기준
public int CompareTo(Info other)
{
// 갯수 기준으로 내림차순, 갯수가 같다면 번호 기준 오름차순
if (other.count == count) return num - other.num;
return other.count - count;
}
}
public int[] solution(int e, int[] starts)
{
List<Info> dp = new List<Info>();
dp.Add(new Info(0,0)); // 첫번째 의미없는 배열 채워줌(인덱스 채우기용)
// 각 dp 배열 만들어줌
for (int i = 1; i <= e; i++) dp.Add(new Info(i,0));
// 각 숫자가 나온 횟수 구하기
for (int i = 2; i <= e; i++)
{
for (int j = 1; j <= e; j++)
{
if (i * j > e) break;
dp[i * j].count++;
}
}
dp.Sort(); // 정렬 기준에 따라 정렬
int[] answer = new int[starts.Length];
for(int i = 0; i < starts.Length; i++)
{
int s = starts[i];
// 앞에 있을수록 나온 횟수가 많고, 번호가 작은 것
for (int j = 0; j <= e; j++)
{
// 그게 s보다 크다면 그게 정답
if (s <= dp[j].num)
{
answer[i] = dp[j].num;
break;
}
}
}
return answer;
}
}
C++은 괜찮았는데, C#은 같은 방식을 사용하면 진짜 겨우 통과한다.
그래서 두 번째 풀이가 필요하다고 생각했다.
2번 방식 풀이
using System;
public class Solution {
public int[] solution(int e, int[] starts) {
int minS = starts[0];
// 시간을 줄이기 위해 S중 가장 작은 값을 도출
foreach (int s in starts) minS = Math.Min(minS, s);
int[] arr = new int[e + 1];
int[] dp = new int[e + 1];
// 각 숫자의 개수를 도출
for(int i = 2; i <= e; i++)
for (int j = 1; j <= e; j++){
if(i * j > e) break;
arr[i*j]++;
}
// dp 초기화
for(int i = 1; i <= e; i++) dp[i] = i;
// e-1부터 역순으로 탐색
for (int i = e-1; i >=minS ; i--)
{
if (arr[i] >= arr[dp[i + 1]]) dp[i] = i;
else dp[i] = dp[i + 1];
}
// 찾은 값 채워넣기
int[] answer = new int[starts.Length];
for (int i = 0; i < starts.Length; i++) answer[i] = dp[starts[i]];
return answer;
}
}
↑
시행착오
필자는 일단 첫 번째 풀이로 풀었다.
근데 아무리 해봐도 시간초과가 나서 실패했다.
그리고 C#으로 먼저 풀었는데,
이게 만약 C++로 풀었다면 정답을 받았을 코드라는 게 너무 짜증 난다.
두 번째 방법은 아래 링크의 블로거님의 방식이 많이 참고가 되었다.
덕분에 이 문제가 단순 수학 문제가 아님을 알 수 있게 되었다.
https://velog.io/@aoleejohn/C-프로그래머스-억억 단을-외우자
C++:: 프로그래머스 < 억억단을 외우자 >
생각보다 간단한 문제인데 시간초과 때문에 애를 먹은 문제이다. 핵심적인 문제의 풀이는 해당 구간의 수들중 약수의 개수가 가장 큰 값(중복이면 작은 값)을 찾아주면 되는 문제이다. 이때 해
velog.io
생활비..