[Problem Solving] 프로그래머스 77884 약수의 개수와 덧셈

약수의 개수와 덧셈 문제에 대한 설명은 다음의 링크를 참고해주시기 바랍니다. 문제 설명

코딩테스트 연습 - 약수의 개수와 덧셈

left와 right 사이의 정수에 대해서 약수의 개수를 세어주고, 약수의 개수가 홀수라면 빼고 짝수라면 더한 결과를 출력해주는 문제입니다.

 

문제를 해결하기 위해서는 약수를 모두 세어줘야 한다고 생각하여 1을 제외한 모든 수의 약수를 세어주어 문제를 해결하였습니다.

 

약수의 개수를 세어줄 때에는 1부터 자기 자신까지 순환해주는 방법이 아니라 1을 제외한 모든 정수는 1과 자기 자신을 포함하는 것을 이용하여 미리 추가해주고, 나머지 2~number//2까지 숫자에 대해서만 순환하여 개수를 구하였습니다.

 

다음은 제가 작성한 코드입니다.

 

def get_alquit_by(number):
  alquit = [1, number]

  for i in range(2, number//2+1):
    if number % i == 0:
      alquit.append(i)
  return alquit

def solution(left, right):
  answer = 0
  for number in range(left, right+1):
    if number == 1: count = 1
    else: count  = len(get_alquit_by(number))

    answer += number if count % 2 == 0 else -number
  return answer

 

정수 1을 get_alquit_by(1)로 계산하면 결과는 [1,1]이 나오게 됩니다. 따라서 조건문을 사용하여 number==1이 참인 경우에는 약수의 개수를 1로 초기화하도록 설정하여 문제가 발생하지 않도록 해주었습니다.

 

문제를 해결한 후에 "다른 사람의 풀이"를 확인한 결과 문제 해결 과정에서 보지 못한 핵심이 있었습니다. 바로 약수는 대응된다는 것입니다. 예시를 통해 확인해보면 18의 경우 [1,2,3,6,9,18]의 약수를 가지고 각각은 1 * 18, 2 * 9, 3 * 6처럼 대응이 됩니다. 다음은 16의 경우입니다. 16은 [1,2,4,8,16]의 약수를 가지고 각각은 1 * 16, 2 * 8, 4 * 4로 대응됩니다.

 

눈치가 빠른 분들은 위의 16, 18의 차이점을 알아챘을 겁니다. 차이점은 바로 i * i로 대응되는 패턴이 있는지 여부입니다. 18의 경우 i * i 패턴이 존재하지 않으므로 약수의 개수가 짝수입니다. 반대로 16은 i * i 패턴을 가지고 있으므로 약수의 개수가 홀수 입니다.

 

i * i 패턴을 찾는 법은 number에 루트를 씌운 값이 정수인지를 판별하는 것으로 알아낼 수 있습니다. 위의 방법을 코드로 표현한다면 다음과 같습니다.

 

def best_solution(left, right):
  answer = 0
  for number in range(left, right+1):
    if int(number**0.5) == number**0.5:
      answer -= number
    else:
      answer += number
  return answer

 

코드가 훨씬 간결해졌습니다. 문제의 요구사항은 약수의 개수가 중점적이지 무슨 약수를 가지고 있는지를 확인하지 않습니다. 따라서 첫 번째 풀이(모든 약수의 개수를 세어주는 방법)보다는 두 번째 풀이가 문제가 원하는 정답에 가까울 것으로 판단됩니다.

 

level 1 문제라서 빠른 풀이가 보여 문제 해결하기 위한 핵심을 생각하지 않아 문제의 핵심을 관통하는 방법으로 해결하지는 못 했습니다. 앞으로는 문제의 입력값과 문제가 원하는 답을 잘 분석하여 핵심을 찾아보는 습관을 가져야 할 것 같습니다.