[Python] programmers, 기사단원의 무기 Lv.1 (feat.시간 초과)

반짝반짝 알고리즘, 인프준

 

기사단원의 무기

문제 링크

프로그래머스

 

문제 설명

숫자나라 기사단의 각 기사에게는 1번부터 'number'까지 번호가 지정되어 있습니다. 기사들은 무기점에서 무기를 구매하려고 합니다.

 

각 기사는 자신의 기사 번호의 약수 개수에 해당하는 공격력을 가진 무기를 구매하려 합니다. 단, 이웃나라와의 협약에 의해 공격력의 제한수치를 정하고, 제한수치보다 큰 공격력을 가진 무기를 구매해야 하는 기사는 협약기관에서 정한 공격력을 가지는 무기를 구매해야 합니다.

 

예를 들어, 15번으로 지정된 기사단원은 15의 약수가 1, 3, 5 ,15로 4개 이므로, 공격력이 4인 무기를 구매합니다. 만약, 이웃나라와의 협약으로 정해진 공격력의 제한수치가 3이고 초과한 기사가 사용할 무기의 공격력이 2라면, 15번으로 지정된 기사단원은 무기점에서 공격력이 2인 무기를 구매합니다. 

 

무기를 만들 때, 무기의 공격력 1당 1kg의 철이 필요합니다. 그래서 무기점에서 무기를 모두 만들기 위해 필요한 철의 무게를 미리 계산하려 합니다.

 

기사단원의 수를 나타내는 정수 'number'와 이웃나라와 협약으로 정해진 공격력의 제한수치를 나타내는 정수 'limit'와 제한수치를 초과한 기사가 사용할 무기의 공격력을 나타내는 정수 'power'가 주어졌을 때, 무기점의 주인이 무기를 모두 만들기 위해 필요한 철의 무게를 retrun 하는 solution 함수를 완성하시오.

 

제한 조건

1 <= number <= 100,000

2 <= limit <= 100

1 <= power <= limit

 

 

입출력 예

number	limit	power	result
5	3	2	10
10	3	2	21

 

입출력 예 설명

입출력 예#1

1부터 5까지의 약수의 개수는 순서대로 [ 1, 2, 2, 3, 2 ] 개입니다. 모두 공격력 제한 수치인 3을 넘지 않기 때문에 필요한 철의 무게는 해당 수들의 합인 10이 됩니다. 따라서 10을 return 합니다.

 

입출력 예#2

1부터 10까지의 약수의 개수는 순서대로 [ 1, 2, 2, 3, 2, 4, 2, 4, 3, 4 ] 개입니다. 공격력의 제한수치가 3이기 때문에 6, 8 ,10번 기사는 공격력이 2인 무기를 구매합니다. 따라서 해당 수들의 합인 21을 return 합니다.

 

 

 

해결 과정

문제를 읽고 이해한 내용을 요약 정리하는 것부터 시작해 봅니다.

1. 1부터 'number'까지 모든 수의 약수를 구한다.
2. 약수의 수가 'limit' 보다 크면 'power'값으로 대체한다.
3. 구해진 모든 수의 합을 반환한다.

    divisors = []                   # 약수 list
    for i in range(1, number+1):    # 1부터 number까지 for loop
        divisor = 0                 # i번째 수의 약수 count
        for j in range(1, i+1):     # 1부터 i까지 for loop
            if i % j == 0:          # i 나누기 j의 나머지가 0이면 약수
                divisor += 1
        if divisor > limit:         # 공격력 제한수치보다 높은지 확인
            divisor = power         # 높다면 power값 으로 대체
        divisors.append(divisor)
    return sum(divisors)

 

 

위 코드는 논리적으로 문제가 없기에 테스트 케이스에서 실행 성공했지만 2중 for loop을 사용함으로써 O(n²)의 시간 복잡도를 가지게 됩니다. 'number' 값이 커질수록 실행시간이 커지기 때문에 시간 초과가 발생하게 됩니다.

 

 

2중 for loop을 사용해서 제출한 결과

 

 

시간 초과문제를 해결하기 위해 약수의 개수를 구하는 문제에서 중요한 2가지가 있습니다. 

 

# Key Point 1
약수는 짝이 맞춰서 있기 때문에 for loop에서 'number'의 제곱근까지만 반복하는 것입니다.
예시로 20의 제곱근은 4.4xxx 입니다. 이때 [ 1, 2, 4 ]가 약수로 구해지고 20을 구해진 약수로 나눈 [ 20, 10, 5 ]가 구해집니다. 이렇게 제곱근 이상의 값까지 반복하지 않아도 총 6개의 약수가 불필요한 연산 없이 구해집니다.

# Key Point 2
문제를 잘 읽고 제한조건을 활용하는 방법입니다.
문제에서 'limit'의 값을 초과하면 'power'값으로 대체하라는 조건이 있습니다. for loop과정에서 divisor의 카운트가 limit을 넘어가면 power을 리턴하면서 강제 종료를 함으로써 연산의 수를 줄일 수 있습니다.

 

2가지 Key Point를 적용하여 작성한 코드와 결과를 확인해 보겠습니다.

 

def solution(number, limit, power):
    divisors = []                             # 약수 list
    for i in range(1, number+1):              # 1부터 number까지 for loop
        divisor = 0
        for j in range(1, int(i**(1/2)) + 1): # 1부터 i의 제곱근까지 for loop
            if i % j == 0:
                divisor += 1
                if j**2 != i:                 # 제곱이 되는 수는 count 1을 하여 중복 방지.
                    divisor += 1
            if divisor > limit:               # limit값을 초과하면 power값으로 return
                divisor = power
                break
        divisors.append(divisor)
    return sum(divisors)

 

 

또 다른 풀이

def cf(n): # 공약수 출력
    a = []
    for i in range(1,int(n**0.5)+1):
        if n%i == 0:
            a.append(n//i)
            a.append(i)
    return len(set(a))
def solution(number, limit, power):
    return sum([cf(i) if cf(i)<=limit else power for i in range(1,number+1)])

 

 

위 코드는 set 함수로 중복되는 값을 제거해서 제곱수를 해결하는 방법입니다. 알고리즘은 이해가 안 될 때는 정말 지루하고 재미없지만 이해하고 나면 세상 재밌는 묘한 매력을 가지고 있었음을 다시 한번 느끼게 해 준 문제였습니다. 또한 기술적인 최적화 작업을 진행하기 전에 문제를 바라보는 시각과 이해하는 능력의 중요함을 강조하게 됩니다.

 

 

 

 

---

 

 

 

 

출처: 프로그래머스 코딩 테스트 연습,&nbsp; https://school.programmers.co.kr/learn/challenges