mminky's

Code

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

Result

Time Out 에러가 났다..(๑•́₋•̩̥̀๑)

<문제 해결 아이디어>

N개의 카운터인 vector<int> counter(N);을 생성한다.

이때 default값인 0으로 초기화된다.

돌면서 A[i] != N+1일 경우 A[i]번째(index로는 A[i]-1) 카운터에 +1을한다.

그리고 counter[ A[i]-1 ]과 max_value 중 더 큰 값을 max_value에 저장한다.

(이때, 시작부터 N+1이 나와도 0000..인 상태에서 최대값은 0이므로 if를 안거치고 바로 else로 간다고 해도 무방하다.)

A[i] == N+1일 경우 저장해두었던 max_value로 모든 값을 초기화시킨다.

그리고 벡터형태로 return하라고 했으므로 return counter;를 해준다.

* else부분에서 counter[j] = max_value;를 해야했는데

A[j] = max_value;를 해서 계속 에러가 났다. 배열의 이름을 헷갈리지 않아야겠다.

* vector<int> v(N);을 하면 자동으로 0으로 init되는 것 같다.

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

<해결 아이디어>

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되지 않은 것 같다 :)