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
<해결 아이디어>
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 |