1일 1코딜리티2020. 3. 8. 00:02
728x90

Code

#include <iostream>
#include <vector>
#include <algorithm>

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

 

Result

 

<해결아이디어>

우선 벡터를 정렬한다.

int compare = 1;으로 초기화 한 후 compare를 하나씩 증가시키면서

A[i]값과 일치하는지 확인한다.

즉, 벡터A가 1,2,3,4.. 순인지 확인한다.

 

compare는 1부터 하나씩 증가시키는데 compare != A[i]일 경우 A[i]가 차례대로 증가하지 않았다는 뜻이므로

return 0;을 한다.

하지만 for문을 다 돌았다는 것은 중간에 return되지 않았다는 뜻이므로 permutation임을 뜻한다. 따라서 return 1;을 해준다.

 

<기억하자>

return;

cout<<"hi";

 

return해당 함수를 종료한다.

따라서 다음 문장인 hi를 출력하는 코드는 실행되지 않는다.

반응형

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

[ Lesson 04_3 ] MissingInteger  (0) 2020.03.07
[ 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
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
1일 1코딜리티2020. 3. 1. 20:43
728x90

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되는 것 같다.

반응형

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

[ Lesson 04_4 ] PermCheck  (0) 2020.03.08
[ Lesson 04_3 ] MissingInteger  (0) 2020.03.07
[ 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
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
1일 1코딜리티2020. 2. 27. 15:19
728x90

code

#include<cstdlib>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

int solution(vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)
    int minimal = 999999999;
  
    
    for(int p = 1; p<A.size(); p++){
          int sum_front = 0;
          int sum_back = 0;
        for(int i=p-1; i>=0; i--){
            sum_front += A[i];
        }
        
        for(int j=p; j<A.size(); j++){
            sum_back += A[j];
        }
        
        minimal = min(minimal, abs(sum_front-sum_back));
        
    }
    return minimal;
}

 

result

Time Out Error다.. Killed는 너무 했잖아..(。•́-ก̀。)

 

<해결 아이디어>

p-1 ~ 0까지 합인 sum_front

p ~ A.size()까지의 합인 sum_back의 차를 구한다.

 

이때 int의 절대값을 구하는 abs( , )는 <cstdlib>를 추가해줘야한다.

 

그리고 minimal에 999 999 999를 넣었는데

이는 100,000개가 있고 50,000개가 1000, 50,000개가 -1000일 때 최고 차이가 2000 * 50,000 = 100,000,000가 된다.

따라서 넉넉하게 제일 큰 수를 999,999,999로 설정했다.

 

* sum_front, sum_back 초기화를 p가있는 for문 안에 안 넣어줘서 에러가 떴는데 수정했다.

* 반복문인 for문을 너무 많이 써서 timeout이 된 것 같다. 해결책을 찾아봐야겠다.

반응형

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

[ Lesson 04_2 ] MaxCounters  (0) 2020.03.01
[ Lesson 04_1 ] FrogRiverOne  (0) 2020.03.01
[ Lesson 03_2 ] PermMissingElem  (0) 2020.02.27
[ Lesson 03 ] FrogJmp  (0) 2020.02.26
[Lesson 02_2] Odd Occurences In Array  (0) 2020.02.25
Posted by mminky
1일 1코딜리티2020. 2. 27. 11:37
728x90

code

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

 

Result

규모가 큰 집단에서는 오답이 나왔다.

이유를 찾아봐야겠다.

 

해결 아이디어

: 1~ N+1 까지의 수 중 N개가 배열 A에 들어있다.

 즉, 하나의 수가 제외되어있고 그 수를 찾는 것이 문제이다.

 

그래서 1~N+1의 합에서 각 배열에 들어있는 수를 모두 빼면 남는 값이 제외된 수 일 것이라 생각했다.

1에서 n까지의 합은 n*(n+1)/2 이다.

 

따라서 (N+1)(N+2)/2 - A[i]를 return했다.

 

--------------------------------------------------------------------------------------------------------------------

 

20-02-27 int형에서 long long 형으로 수정

 

정확도에서 100%가 나오는데 큰 규모에서 안 되는 이유가 궁금했다.

그래서 찾아보니 자료형의 차이인 것 같아 long long 형으로 수정을 하고

return할 때만 int로 형변환을 해서 반환했다.

int solution(vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)
    long long N = A.size();
    long long sum = (N+1)*(N+2)/2;
    for(long long i=0; i<N; i++){
        sum -= A[i];
    }
    return (int)sum;
}

 

결과

<요약>

* int : 4바이트 (32/64비트 상관 없이)

signed int(부호가 있는 정수) 기준으로 0 ~ 2,147,483,647(16진수로 7FFFFFFF) 기록 가능

 

* long long : 8바이트

signed long long 기준 0 ~ 9,223,372,036,854,775,807(16진수로 7FFFFFFFFFFFFFFF) 기록 가능

(long long으로도 불가능하면 BigInteger)

( https://www.acmicpc.net/board/view/15516 gallopsys님 답변 참고)

 

즉, large test에서만 에러가 난 이유가 int형으로는 표현이 불가능했기 때문이라고 생각해

long long 타입으로 바꿨다!

반응형

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

[ Lesson 04_1 ] FrogRiverOne  (0) 2020.03.01
[ lesson 03_3 ] TapeEquilibrium  (0) 2020.02.27
[ Lesson 03 ] FrogJmp  (0) 2020.02.26
[Lesson 02_2] Odd Occurences In Array  (0) 2020.02.25
코딜리티(Codility) 사이트  (0) 2020.01.08
Posted by mminky
1일 1코딜리티2020. 2. 26. 22:20
728x90

코드

int solution(int X, int Y, int D) {
    // write your code in C++14 (g++ 6.2.0)
    int jump = 0;
    while( (X + D*jump) < Y ){
        jump ++;
    }
    return jump;
}

결과

 

시간복잡도에서 큰일났다..

다음에 좀 더 효율적인 코드로 다시 도전해봐야겠다!

반응형

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

[ Lesson 04_1 ] FrogRiverOne  (0) 2020.03.01
[ lesson 03_3 ] TapeEquilibrium  (0) 2020.02.27
[ Lesson 03_2 ] PermMissingElem  (0) 2020.02.27
[Lesson 02_2] Odd Occurences In Array  (0) 2020.02.25
코딜리티(Codility) 사이트  (0) 2020.01.08
Posted by mminky
1일 1코딜리티2020. 2. 25. 17:09
728x90

Answer

// you can use includes, for example:
// #include <algorithm>

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

int solution(vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)
    int key=0;
    for(int i=0; i<A.size(); i++){
        key ^= A[i];
    }
    return key;
}

 

Solution Point :

이 문제의 해결 포인트는 다음과 같다.

array A의 모든 원소XOR 했을 때, 홀수개 인 수만 남는다.

 

XOR 테이블

입력 출력
A B F
0 0 0
0 1 1
1 0 1
1 1 0

XOR은 두 수가 같을 경우 0을 출력하고, 다를 경우 1을 출력한다.

즉, 동일 한 수가 두 번 나올 경우 XOR값은 0이 된다.

 

문제에 나온 예시인

9 ⊕ 3 ⊕ 9 ⊕ 3 ⊕ 9 ⊕ 7 ⊕ 9

= 1001 ⊕ 0011 ⊕ 1001 ⊕ 0011 ⊕ 1001 ⊕ 0111 ⊕ 1001

= 0111(2진수) = 7(10진수)

 

첫째자리 : 1 0 1 0 1 0 1 -> 1이 짝수개 -> 0

둘째자리 : 0 0 0 0 0 1 0 -> 1이 홀수개 -> 1

셋째자리 : 0 1 0 1 0 1 0 -> 1이 홀수개 -> 1

넷째자리 : 1 1 1 1 1 1 1 -> 1이 홀수개 -> 1

따라서 결과가 0111 즉, 7로 하나만 있는 수가 나오게 된다.

 

 

반응형

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

[ Lesson 04_1 ] FrogRiverOne  (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
코딜리티(Codility) 사이트  (0) 2020.01.08
Posted by mminky