수학 공식을 활용한 알고리즘

1. 문제

 

https://programmers.co.kr/learn/courses/30/lessons/86051

코딩테스트 연습 - 없는 숫자 더하기

 

0부터 9까지의 숫자 중 일부가 들어있는 배열 numbers가 매개변수로 주어집니다.

 

numbers에서 찾을 수 없는 0부터 9까지의 숫자를 모두 찾아 더한 수를 return하도록 solution 함수를 완성하세요

 

2. 제한사항

 

numbers의 길이는 1이상 9이하

 

numbers의 모든 수는 0이상 9이하

 

numbers의 모든 수는 서로 다름

 

3. 입출력 예시

 

그림1. 입출력 예시

 

4. 나의 풀이

 

습관적으로 0부터 9까지중 없는 것을 for문을 돌면서 찾을 생각하면 하수

 

수학적으로 생각해보면 더한 수를 return해야하면서 numbers의 수는 모두 다르다는 점을 고려해보면

 

역으로 0부터 9까지의 합에서 numbers에 들어간 수의 합을 빼기만 하면 numbers에서 0부터 9중 없는 수들의 합을 구한 것이나 마찬가지

 

def solution(numbers):
    
    total_sum = 9*10/2
    
    total_sum = total_sum - sum(numbers)
    
    return total_sum

 

for문으로 하나씩 빼면서 더할필요도 없이 sum()을 이용하면 리스트에 존재하는 모든 수의 합 바로 구할 수 있음

 

 

5. 되돌아보기

 

완벽하게 풀어가지고 다른 풀이 볼 필요도 없음

 

리스트 보이면 무작정 for문부터 하나씩 빼보겠다고 생각한 것이 아니고 수학적으로 역발상 잘했음

 

for문으로 하나씩 빼면서 sum한것도 아니고 sum()함수로 깔끔하게 구한것도 잘했음

 

1부터 n까지 자연수의 합은? $$\frac{n(n+1)}{2}$$

 

제곱수의 합은? $$\frac{n(n+1)(2n+1)}{6}$$

 

세제곱수의 합은? $$(\frac{n(n+1)}{2})^2$$

 

알고리즘이 for문 돌리고 조건문 쓰고 그런것만 있는 것이 아니라 수학공식을 활용해야할때도 있다는 점 기억하면 좋다