[프로그래머스] 제일 작은 수 제거하기

1. 문제 설명

정수를 저장한 배열, arr 에서 가장 작은 수를 제거한 배열을 리턴하는 함수, solution을 완성해주세요. 단, 리턴하려는 배열이 빈 배열인 경우엔 배열에 -1을 채워 리턴하세요. 예를들어 arr이 [4,3,2,1]인 경우는 [4,3,2]를 리턴 하고, [10]면 [-1]을 리턴 합니다.

 

- 제한 사항

• arr은 길이 1 이상인 배열입니다.
• 인덱스 i, j에 대해 i ≠ j이면 arr[i] ≠ arr[j] 입니다.

2. 풀이 코드

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<int> arr) {
	vector<int> answer = arr;

	if (arr.size() == 1)
		answer = {-1};
	else 
    {
		int minValueIndex = 0;
        
		for (int i = 1; i < answer.size(); i++)
        {
            if(arr[i]<arr[minValueIndex])
                minValueIndex = i;
            
        }
        
        answer.erase(answer.begin()+minValueIndex);
        
	}

	return answer;
}

 

3. 정리

배열의 원소가 1개인 경우에는 유일한 1개가 제거 되므로 -1 배열을 리턴 한다. 그 이외에는 0번 인덱스를 가장 작은 값으로 가정하고 for문으로 1번 인덱스부터 비교하여 작은 인덱스가 있으면 교체하여 최종적으로 배열에서 가장 작은 원소의 인덱스를 찾아 배열에서 해당 원소를 제거한다.

 

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

 

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