'FrogRiverOne'에 해당되는 글 1건

  1. 2020.03.01 [ Lesson 04_1 ] FrogRiverOne
1일 1코딜리티2020. 3. 1. 17:50
728x90

Code

int solution(int X, vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)
    int count[X+1]={0, };
    int sum = 0;
    
    for(int i=0;i<A.size();i++){
        if(count[ A[i] ] == 0){
            count[A[i]] = 1;
            sum++;
        }
        if(sum ==X){
            return i;
        }
    }
    if(sum != X){
        return -1;
    }
}

 

Result

받아도받아도 좋은 PERFECT SCORE :)

 

<해결 아이디어>

1,2,3,...X가 나오는 순간의 i(index)를 찾아서 리턴해야한다.

우선 X+1개의 칸을 가진 배열 count를 0으로 초기화시킨다.

그리고 각 숫자가 나오면 해당 칸을 1로 만든다.

이때 숫자가 중복해서 나올 수 있으므로 count[숫자]==0일 때만 1로 만들고, 총 나온 숫자의 개수인 sum을 증가한다.

 

만약 for문을 다 돌아도 sum이 X가 아닐 경우에는 return -1을 한다.

 

 

* for을 많이 쓰면 time complexity가 증가하고

  if을 쓰면 time complexity가 조금 줄어드는 것 같다.

 

이번에는 적절한 if문의 사용으로 time out되지 않은 것 같다 :)

반응형

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

[ Lesson 04_3 ] MissingInteger  (0) 2020.03.07
[ Lesson 04_2 ] MaxCounters  (0) 2020.03.01
[ lesson 03_3 ] TapeEquilibrium  (0) 2020.02.27
[ Lesson 03_2 ] PermMissingElem  (0) 2020.02.27
[ Lesson 03 ] FrogJmp  (0) 2020.02.26
Posted by mminky