프로그래머스 - 억억단을 외우자 파이썬

문제 

프로그래머스

문제 설명 사진

 

문제 정리 

한 줄 정리

starts의 변수에서 e파라미터까지 범위 숫자의 약수의 개수 중 가장 많은 약수를 가진 숫자를 차례로 반환하는 문제 

 

포인트

- 억억단에서 해당 자연수가 등장하는 횟수 = 악수의 개수와 동일 

예를 들어 

8이 억억단에 등장하는 횟수는 

1*8 

2*4 

4*2

8*1이다 

이는 8의 약수의 개수인 4(1, 2,4,8)와 동일하다

- 시간초과 안 걸리기 = 약수의 개수를 한꺼번에 구하기, 여러 번 돌면 안 됨 

 

문제 풀이 순서 

- 시작은 랜덤이지만 끝지점은 e파라미터로 정해져있음 -> 그래서 1~e까지의 약수 정보를 저장할 리스트 생성 

- 약수 정보를 저장(1~e까지의 각 수의 배수에 대해 증가), 해당 범위에서 약수가 가장 많은 숫자를 찾음 

- 약수의 개수를 기준으로 내림차순 정렬(만약 개수가 같으면 더 작은 수를 반환할 수 있도록)

- 정렬한 배열을 처음부터 탐색해서 최종 답 출력 

- 1부터 e까지 각 숫자의 시작시점에서 배수의 변수에 +1을 하면 모든 숫자에 대한 약수의 개수를 알 수 있음 

 

3단계인 이유

1. 최적화된 약수 카운팅 방법 

2. dp 메모이제이션 필요 

 

제한사항

1<=e <= 5,000,000이라 5백만 단*5백만 단이다 

starts 배열의 길이가 최소 10만임 

배열을 카운팅하는 것은 시간초과 -> dp가 나오는 이유 

 

 

코드 

전체 코드 

def solution(e, starts):
    answer = []
    multiples = [0] * (e + 1)  # 수의 등장 횟수를 기록할 리스트 초기화

    # 배수 세기
    for i in range(1, int(e ** 0.5) + 1):  # 제곱근까지만 반복
        for j in range(i, e // i + 1):  # i 이상 e // i 이하의 수들을 반복
            multiple = i * j  # 배수 계산
            multiples[multiple] += (2 if i != j else 1)  # 중복되지 않는 경우 2를 더하고, 중복되는 경우 1을 더함

    counts = [0] * (e + 1)  # 등장 횟수에 따른 숫자 기록할 리스트 초기화
    max_count = 0

    # 약수의 개수가 큰 순서대로 정렬
    for idx in range(e, 0, -1):  # e부터 1까지 역순으로 반복
        if multiples[idx] >= max_count:
            max_count = multiples[idx]
            counts[idx] = idx
        else:
            counts[idx] = counts[idx + 1]  # 등장 횟수가 이전 값보다 작으면 이전 값으로 갱신

    # 답 목록 구하기
    for start in starts:
        answer.append(counts[start])

    return answer

- multiples 배열 인덱스에는 i*j 할 때 나올 수 있는 경우의 수를 담음 

(i, j가 같으면 경우의 수는 1, 다르면 2가 됨 / 예: i = 3, j = 3이면 경우의 수는 앞뒤 같아서 1이지만, i= 2, j = 3이면 2*3인 경우, 3*2인 경우로 총 2개가 됨) 

 

- multi_value는 숫자가 등장한 최대 횟수값, 현재 수보다 크거나 같으면 갱신됨 

 

-  아래의 반복문에 대한 설명 

    # 약수의 개수가 큰 순서대로 정렬
    for idx in range(e, 0, -1):  # e부터 1까지 역순으로 반복
        if multiples[idx] >= max_count:
            max_count = multiples[idx]
            counts[idx] = idx
        else:
            counts[idx] = counts[idx + 1]  # 등장 횟수가 이전 값보다 작으면 이전 값으로 갱신

idx = 8이면 

multi [8]은 8이 나올 수 있는 경우의 수의 총합, 그러므로 4이다

8이 억억단에 등장하는 횟수는

1*8 

2*4 

4*2

8*1이다  //이렇게 구하는게 번거로워서 그냥 약수의 개수를 구하는 것과 동일함을 알게 됨 

max_value=0보다 큼

그래서 max_value는 4로 갱신됨 

가장 많이 나온 숫자는 8이라서 counts[8]도 8이 됨 

 

idx = 7이라면 

multi[7]은 2 임 //7의 약수는 1, 7 단 2개뿐임

max_value=4보다 작아서 갱신 안됨 

현재 7~8 중 더 많이 나온 숫자는 8이라서 count[8]은 8 임 

 

idx = 6이라면 

multi[6] = 4 임 

크거나 같으면 max_value가 갱신되므로 이번에 4로 갱신됨 

그래서 count[6] = 6이 됨 

6~8인 수 중에서 가장 많이 나오면서 작은 수는 6이 됨 

 

이 것을 계속 반복해서 최종적으로 리턴함