프로그래머스 여섯 번째 문제: 기사단원의 무기(Level 1)

 

안녕하세요. 오늘은 Level 1 문제인 기사단원의 무기 문제를 풀어보려고 합니다.

 

 

문제 자체가 어렵진 않지만, 소수의 개수를 구하는 문제로 소수 구하는 방법에 대해서 다뤄보고자 합니다.

 

 

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

프로그래머스

 

 

풀이:

def solution(number, limit, power):
    # number : 기사단원의 수
    # limit: 공격력 제한 수치
    # power: 제한 수치를 초과한 기사가 사용할 무기
    answer = 0
    num_lst = []
    
    # 약수 개수 구하기
    for n in range(1, number + 1):
        prime_num = []
        for i in range(1, int((n**0.5) + 1)):
            if n % i == 0:
                prime_num.append(i) # 앞쪽
                if i != n // i:
                    prime_num.append(n // i) # 뒤쪽

        num_lst.append(len(prime_num)) # 약수 개수 정리
    
    # 약수 개수 모아놓고 limit 넘으면 교체
    for idx, p in enumerate(num_lst):
        if p > limit:
            num_lst[idx] = power
        
    return sum(num_lst)

약수를 구할 때, 1부터 n까지 다 따지면서 나눠지는지 여부를 확인하는 것이 소수의 원리에 맞는 방법입니다.

 

하지만, 코딩테스트에서 다루는 문제들은 대부분 시간복잡도 문제가 있어 이를 그대로 다 계산하면 시간복잡도 제한에 걸리게 됩니다.

 

위 문제도 당연히 시간복잡도 이슈에 직면하게 됩니다.

 

 

하나의 수는 보통 약수의 짝이 존재합니다.

 

예를 들어, 8의 약수를 구한다고 한다면 1, 2, 4, 8가 되는데, 1과 8 / 2와 4는 각각 짝으로 생각할 수 있습니다.

 

따라서, 약수를 구할 때 1부터 8까지 모두 따지는 것보다 짝이 있다는 개념을 활용해서 이를 조금 더 빠르게 판단할 수 있습니다.

 

 

그래서 보통 사용하는 방법은, 구하려고 하는 수의 제곱근을 계산하여 제곱근 까지만 계산해 보는 방법입니다.

 

제곱근이 직관적인 16을 예시로 들겠습니다.

 

16의 약수는 1, 2, 4, 8, 16입니다. 위에서 설명드린 바와 같이, 1과 16 / 2와 8은 짝입니다. 4는 4와 짝이지만 같은 수 이므로 한 번만 카운팅 하게 되지요.

 

이처럼 어떤 수의 약수를 생각할 때는, 어떤 수의 제곱근 까지만 생각하면 모든 약수를 구할 수 있다는 것입니다.

 

 

이를 코드로 구현한 부분이 이것입니다.

for i in range(1, int((n**0.5) + 1)):
    if n % i == 0:
        prime_num.append(i) # 앞쪽
        if i != n // i:
            prime_num.append(n // i) # 뒤쪽

우리가 구하려는 수는 n이고, n의 제곱근 까지만 반복문을 진행한다는 사실을 알 수 있습니다.

 

n이 i로 나눠지면, 이를 prime_num이라는 list에 저장합니다.

 

그리고 이 경우에, 만약 i가 n을 i로 나눈 몫과 같지 않으면, n을 i로 나눈 몫을 소수로 추가합니다.

 

 

이를 16을 예시로 들어 설명 드리겠습니다.

 

for i in range(1, 4+1) 이 될 것이고, 첫 번째로 16이 1로 나눠지는지를 검토합니다. 이때 나눠지므로, 소수로 인정합니다.

 

그리고 1이 16을 1로 나눴을 때의 값과 다른지 확인합니다. 이 때는 다르므로, 16을 1로 나눈 16도 소수로 인정합니다.

 

두 번째로 16이 2로 나눠지는지를 검토합니다. 이 때 나눠지므로, 소수로 인정합니다.

 

그리고 2가 16을 2로 나눴을 때의 값(8)과 다른지 확인, 다르므로 8도 소수로 인정합니다.

 

세 번째로 16이 3으로 나눠지는지를 검토합니다. 안되므로 넘어갑니다.

 

네 번째로 16이 4로 나눠지는지를 검토합니다. 이 때 나눠지므로, 소수로 인정합니다.

 

그리고 4가 16을 4로 나눴을 때의 값과 다른지 확인합니다. 이 때는 같기 때문에 소수에 추가하지 않습니다.

 

if i != n // i를 하는 이유를 4의 케이스를 생각해 보시면 이해가 빠를 것 같습니다.

 

 

문제에서 일단 약수의 개수를 list로 만들어주고, limit보다 큰 경우는 power라고 하는 변수 값으로 바꿔준 다음 sum 해주면 문제 풀이는 끝이 납니다.

 

사실상 시간 복잡도의 제약에 걸리지 않고 소수의 개수를 구할 수 있는지가 관건인 문제라고 보시면 됩니다.

 

 

오늘 문제는 여기까지 하겠습니다.