[프로그래머스] 없는 숫자 더하기

1. 문제 설명

0부터 9까지의 숫자 중 일부가 들어있는 정수 배열 numbers가 매개변수로 주어집니다. numbers에서 찾을 수 없는 0부터 9까지의 숫자를 모두 찾아 더한 수를 return 하도록 solution 함수를 완성해주세요.

 

- 제한 사항

• 1 ≤ numbers의 길이 ≤ 9
• 0 ≤ numbers의 모든 원소 ≤ 9
• numbers의 모든 원소는 서로 다릅니다.

2. 풀이 코드

#include <string>
#include <vector>

using namespace std;

int solution(vector<int> numbers) {
	int answer = 45;


	for (int i = 0; i < numbers.size(); i++) 
        answer -= numbers[i];

	return answer;

}

 

3. 정리

제한 사항을 보면 길이는 최대 9이며, 원소는 서로 다르다. 즉, 최악의 경우 배열안에 0~9까지의 숫자가 각각 들어간다. 이 문제는 간단히 해결하기 위해 최악의 경우 원소들의 총합인 45에서 numbers 배열에 있는 원소들을 빼면 없는 숫자들의 총합이 나오게 된다!

 

전체 시간 복잡도는 배열의 원소의 갯수만큼 순회하므로  O(n) 이다.

 

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