[프로그래머스] 억억단을 외우자 파이썬 풀이

※사용언어 : 파이썬 ※

 

▼ 문제 링크 ▼

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

프로그래머스

 

---

 

문제설명

◇  문제를 요약하자면 다음과 같습니다.

▶ 구구단 같이, 억 X 억을 곱해둔 단이 존재합니다. 그리고 해당 억억단에서 s 부터 e까지의 수 중 가장 많이 나온 수를 찾고 출력합니다. 단, s 부터 e까지의 수 중 가장 많이 나온 수가 여러 개이면 가장 작은 수를 출력합니다. (여기서 s는 starts 배열 안의 수다.)

 

◇ 풀이 방법을 간단하게 요약하자면 다음과 같습니다.

▶  문제 조건에 의해 최대로 나오는 수는 e 이기 때문에, 억억단에서 1부터 e까지의 수가 나오는 횟수를 구합니다. 그리고 그걸 이용해 s ~ e 구간에서 가장 많이 나온 수를 구합니다. (풀이 방법의 자세한 사항은 코드와 함께 설명하겠습니다.)

 

---

 

문제풀이(With Python)

def solution(e, starts):
    answer = []

    multi = [0 for _ in range(e+1)]
    # step 1
    for i in range(1, e+1):
        for j in range(i, e+1):
            temp = i*j
            if temp > e:
                break
            if i == j:
                multi[temp] += 1
            else:
                multi[temp] += 2

    count = [0 for _ in range(e+1)]
    max_value = 0
    # step 2
    for idx in range(e, 0, -1):
        if multi[idx] >= max_value:
            max_value = multi[idx]
            count[idx] = idx
        else:
            count[idx] = count[idx+1]

    for start in starts:
        answer.append(count[start])
    return answer

◇ Step 1

▶multi 배열 index에는 i * j를 할 때 index값이 나올 수 있는 경우의 수를 저장합니다. 

1) 예를 들어 i = 2 이고 j = 2경우, i * j = 4입니다. i * j 나 j * i 나 2 * 2이기 때문에 현재 상태에서 4가 나올 경우의 수는 1개이기 때문에 1을 더해줍니다.

2) 다른 예로 i = 3 이고 j = 5인 경우, i * j 는 3 * 5 = 15 지만 j * i 는 5 * 3 = 15 입니다. 따라서 현재 상황에서 15가 나올 경우의 수는 2개이기 때문에 2를 더해줍니다. 

 

◇ Step 2

▶ multi 배열로 각 숫자가 나올 경우의 수를 구했습니다. 이제 그 숫자들 중에서 가장 자주 나온 값을 찾아야 합니다.

▶ starts 안에 있는 수는 e 보다 작습니다. => 문제 조건에 의해 그럴 수 밖에 없습니다.

0 ~ e까지의 수를 확인하다 보면 자연스럽게 starts안에 있는 값을 전부 순회하게 됩니다.

▶ max_value는 숫자가 등장한 최대 횟수값이며, 현재 가지고 있는 수와 같거나 더 큰 횟수를 가진 숫자가 나오면 갱신됩니다.

▶ for 문을 한 번 확인해 봅시다.

1) idx = 8 일 때, multi[8] 은 8이 나올 수 있는 경우의 수의 총합입니다. 8은 총 4번 나오기 때문에, multi[8] = 4 이고 이 값은 max_value = 0보다 큽니다. max_value는 4로 갱신됩니다. 현재 가장 많이 나온 숫자는 8이기 때문에 count[8] 에는 8이 들어갑니다.

2) idx = 7 인 경우, multi[7] = 2입니다. 2는 max_value = 4보다 작기 때문에 갱신되지 않습니다.

7 ~ 8 사의 수 중 억억 단에서 가장 많이 나온 수는 8 이기 때문에 count[7] = 8 이 됩니다.

3) 그럼 여기서 한 가지 의문점이 생깁니다. 왜 for 문이 거꾸로 갈까요? 그건 문제 조건 때문입니다. 문제 조건에 의하면, 가장 많이 등장한 숫자가 여러 개인 경우, 가장 작은 수를 출력하도록 되어있습니다. 그렇기 때문에 for문이 거꾸로 갑니다. 잘 이해가 안 되신다면 다음 단계를 읽어주세요.

4) idx = 6 인 경우, multi[6] = 4 입니다. max_value는 multi[idx]값과 비교해서 자기가 가진 수랑 같거나 큰 경우 갱신됩니다. 이때 같은 수가 나올 때도 갱신하는 이유가 나옵니다.

우리는 등장하는 횟수가 같다면 더 작은 숫자를 반환해야 하기 때문에 횟수가 같은 것도 같이 확인하는 겁니다. 이렇게 max_value는 4로 갱신되고 (이전부터 max_value의 값은 4였지만, 4를 새롭게 할당했기 때문에 갱신했다고 합시다.) count[6] = 6이 됩니다. 이렇게 되면, 6 ~ 8 사이의 수 중에 억억 단에서 가장 자주 등장한 수이면서 가장 작은 수는 6이 됩니다.

5) 이렇게 각 스탭을 반복하다 보면 각 숫자 범위마다 가장 자주 등장하며 가장 작은 수를 구할 수 있습니다.

+) muitl 변수 안에 숫자들이 이해가 안 된다면, 직접 1단부터 8단까지의 수를 적고 숫자를 세어보는 것을 추천드립니다.