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
