mminky's

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를 출력하는 코드는 실행되지 않는다.

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

#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이 된 것 같다. 해결책을 찾아봐야겠다.

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 테이블

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로 하나만 있는 수가 나오게 된다.