[프로그래머스] 나누어 떨어지는 숫자 배열

1. 문제 설명

array의 각 element 중 divisor로 나누어 떨어지는 값을 오름차순으로 정렬한 배열을 반환하는 함수, solution을 작성해주세요.
divisor로 나누어 떨어지는 element가 하나도 없다면 배열에 -1을 담아 반환하세요.

 

- 제한 사항

• arr은 자연수를 담은 배열입니다.
• 정수 i, j에 대해 i ≠ j 이면 arr[i] ≠ arr[j] 입니다.
• divisor는 자연수입니다
• array는 길이 1 이상인 배열입니다.
  
  

2. 풀이 코드

#include <string>
#include <vector>
#include <algorithm>


using namespace std;

vector<int> solution(vector<int> arr, int divisor) {
	vector<int> answer;
    
    
    for(int item : arr)
    {
        if(item % divisor == 0)
            answer.push_back(item);
    }
    
    if(answer.size() > 0)
        sort(answer.begin(), answer.end());
    else
        answer.push_back(-1);
    

	return answer;
}

 

3. 정리

for문을 이용하여 각 원소를 divisor와 나머지 연산하여 0으로 나누어 떨어지면 answer 벡터배열에 넣고 sort 함수를 통해 오름차순 정렬한다. 

 

 

전체 시간 복잡도는 단계별로 분석하면

단계	시간복잡도
for 루프	O(n)
정렬 (sort)	O(최악 O(n log n))  [algorithm 헤더의 sort는 퀵정렬을 사용]
빈 배열 처리 (else)	O(1)

전체 시간복잡도는 O(n log n) 이다.

 

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