'배열정렬'에 해당되는 글 1건

  1. 2020.03.07 [ Lesson 04_3 ] MissingInteger
1일 1코딜리티2020. 3. 7. 22:26
728x90

Code

#include <iostream>
#include <algorithm>
#include <vector>
int solution(vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)
    sort(A.begin(),A.end());
    int min_num=1;
    
    for(int i=0;i<A.size();i++){
        if(A[i]>=1){ //A[i]>0
            if(A[i]==min_num){
                min_num++;
            }
        }
    }
    return min_num;
}

 

Result

 

[해결 아이디어]

1) 오름차순 정렬 -> 빠진 수 찾기

2) 정렬 없이 1있으면 2, 2있으면 3.. -> 1 3 6 4 1 2 일 때 13641까지는 괜찮은데 2가 나오면 다시 2로 해서 찾아야함

3) A랑 같은 사이즈의 'check'벡터를 만든 후 1이 있으면 1넣고.. -> check돌면서 제일 적은 index의 0 찾기

 

이렇게 여러 아이디어 중 정렬을 한 후 빠진 수를 찾는 것이 가장 time complexity가 적을 것 같아서 1번으로 정했다.

 

* 0보다 큰 양의 정수를 return하라고 했으므로 음수의 경우 무조건 1이상의 수를 return 해야한다.

그래서 min_num = 1;로 초기화 해 준 후,

A[i]가 1보다 큰 양의 정수일 때 min_num = min_num +1;을 해주었다.

 

 

 

벡터 정렬 (vector<int> &A)

#include <iostream>

#include <vector>

#include <algorithm>

 

sort( A.begin(), A.end() );

 

 

배열 정렬 (int A[배열크기])

#include <iostream>

#include <algorithm>

 

sort( A, A+배열크기 );

반응형

'1일 1코딜리티' 카테고리의 다른 글

[ Lesson 04_4 ] PermCheck  (0) 2020.03.08
[ Lesson 04_2 ] MaxCounters  (0) 2020.03.01
[ Lesson 04_1 ] FrogRiverOne  (0) 2020.03.01
[ lesson 03_3 ] TapeEquilibrium  (0) 2020.02.27
[ Lesson 03_2 ] PermMissingElem  (0) 2020.02.27
Posted by mminky