코딩테스트 준비하기 - (1) Arrays

코딩테스트를 준비할 일이 생겼다. Codility를 통해 공부하자. 어제 아주 기본적인 문제를 풀었는데 정확도가 80%밖에 되지 않았다 제길ㅠ 한창 코테 준비할땐 그래도 나쁘지 않았던 것 같은데… 계속하지 않으면 금방 까먹는 듯 하다.

난이도별로 여러개의 예제가 엄선되어 있어서 좋다. 백준의 경우에는 너무 많은 예제가 중구난방으로 있어서 뭘 풀어야 할지 감을 잡기 어려운데 그런면에서 훨씬 잘되어 있는 것 같다. 알고리즘에는 역시 C지! 익숙한 C언어로 풀어보자.

Question1 - Cyclic Rotation

An array A consisting of N integers is given. Rotation of the array means that each element is shifted right by one index, and the last element of the array is moved to the first place. For example, the rotation of array A = [3, 8, 9, 7, 6] is [6, 3, 8, 9, 7] (elements are shifted right by one index and 6 is moved to the first place).

The goal is to rotate array A K times; that is, each element of A will be shifted to the right K times.

Write a function:

class Solution { public int[] solution(int[] A, int K); }

that, given an array A consisting of N integers and an integer K, returns the array A rotated K times.

For example, given

    A = [3, 8, 9, 7, 6]
    K = 3
the function should return [9, 7, 6, 3, 8]. Three rotations were made:

    [3, 8, 9, 7, 6] -> [6, 3, 8, 9, 7]
    [6, 3, 8, 9, 7] -> [7, 6, 3, 8, 9]
    [7, 6, 3, 8, 9] -> [9, 7, 6, 3, 8]
For another example, given

    A = [0, 0, 0]
    K = 1
the function should return [0, 0, 0]

Given

    A = [1, 2, 3, 4]
    K = 4
the function should return [1, 2, 3, 4]

Assume that:

N and K are integers within the range [0..100];
each element of array A is an integer within the range [−1,000..1,000].
In your solution, focus on correctness. The performance of your solution will not be the focus of the assessment.

• Array를 받는다
• Array를 Rotate 한다는것은 오른쪽으로 한칸 미는것을 의미 -> 바보같이 왼쪽으로 한칸 미는걸로 풀어서 헤맸다
• Array를 K번 Rotate한 결과를 리턴한다.

문제 solution에서 vector array를 사용한다. 오랜만에 vector를 보니 잘 기억나지 않아서 정리!

http://www.cplusplus.com/reference/vector/vector/

/** 벡터의 선언 */
vector<int> v;        //int형 백터 생성
vector<int>v(4);    //int형 백터 생성 후 크기를 4로 할당(모든 백터요소 0으로 초기화)
vector<int>v = { 1, 2, 3};        //int형 백터 생성 후 1, 2, 3 으로 초기화
vector<int>v[] = {{ 1, 2}, {3, 4}};        //int형 백터 배열 생성(행은 가변이지만 열은 고정)
vector<vector<int>> v;        //2차원 백터 생성(행과 열 모두 가변)
vector<int> v = { 1, 2, 3, 4, 5};        
v.assign(5, 10);    //백터 범위를 5로 지정하고 정수 10으로 초기화

/** 벡터의 사용 */
v.begin();		//벡터 시작점의 주소값 반환(Start index of an array)
v.end();		//벡터 끝부분+1의 주소값 반환(Length of an array)

Solution

vector<int> solution(vector<int> &A, int K) {
    // write your code in C++14 (g++ 6.2.0)
    int arrLen = A.size();
    int startIdx = arrLen - K;
    int endIdx = arrLen - 1;

    if(arrLen == 0) return vector<int>(0);
    
    if(arrLen < K) {
        startIdx = arrLen - (K % arrLen);
    }

    vector<int> ret;
    for(int i = startIdx; i<=endIdx; i++){
        ret.push_back(A[i]);
    }
    for(int j = 0; j<startIdx; j++){
        ret.push_back(A[j]);
    }

    return ret;
}

• 인덱스만 찾는다
• empty array에 대한 예외처리 잊지말자!

Question 2 - Odd occurencies in array

A non-empty array A consisting of N integers is given. The array contains an odd number of elements, and each element of the array can be paired with another element that has the same value, except for one element that is left unpaired.

For example, in array A such that:

  A[0] = 9  A[1] = 3  A[2] = 9
  A[3] = 3  A[4] = 9  A[5] = 7
  A[6] = 9
the elements at indexes 0 and 2 have value 9,
the elements at indexes 1 and 3 have value 3,
the elements at indexes 4 and 6 have value 9,
the element at index 5 has value 7 and is unpaired.
Write a function:

class Solution { public int solution(int[] A); }

that, given an array A consisting of N integers fulfilling the above conditions, returns the value of the unpaired element.

For example, given array A such that:

  A[0] = 9  A[1] = 3  A[2] = 9
  A[3] = 3  A[4] = 9  A[5] = 7
  A[6] = 9
the function should return 7, as explained in the example above.

Write an efficient algorithm for the following assumptions:

N is an odd integer within the range [1..1,000,000];
each element of array A is an integer within the range [1..1,000,000,000];
all but one of the values in A occur an even number of times.

• non-empty array는 N개의 원소로 이루어져있다.
• N개의 원소는 각자 짝이 있다
• 짝이 없는 원소 한개를 찾아라

My Solution(67%)

#include <map>
#include <algorithm>

int solution(vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)
    // Unpaired value일 확률이 있는 값들의 집합
    vector<int> unpaired;

    // 숫자 k, k의 등장횟수
    map<int, int> memory;

    for(int i=0; i<A.size(); i++){
        int k = A[i];
        memory[k]++;

        if(memory[k] % 2 == 1){
            // odd occurency
            unpaired.push_back(k);
        }
        else {
            unpaired.erase(remove(unpaired.begin(), unpaired.end(), k), unpaired.end());
        }
    }

    return unpaired[0];
}

• 로직 자체는 맞지만 원소개수가 많아지면 타임아웃에러 발생. O(N**2)

Other Solution(100%)

• 아이디어가 좋네..
• 받아온 배열을 정렬한다. 정렬한 배열은 인덱스 0에서부터 2개씩 건너뛰며 루프를 돌린다.
• 현재 값이 다음값과 다르면 얘는 홀수개인놈. 얘 이후로는 쭉 인덱스가 깨져서 짝수개로 pair가 나뉘지 않는다.
• 현재값이 마지막 값이면 얘가 홀수개인놈.

def test3(A):
    if len(A) == 1:
        return A[0]

    A = sorted(A)
    print(A)
    for i in range(0, len(A), 2):
        if i+1 == len(A):
            return A[i]
        if A[i] != A[i+1]:
            return A[i]

test3([1,2,1,2,3])

My Solution 2(100%)

• c++의 sort함수는 기본적으로 오름차순 정렬을 수행한다.
• sort(배열 시작주소, 배열 마지막주소 + 1)

int solution(vector<int> &A){
    sort(A.begin(), A.end());

    for(int i=0; i<A.size(); i+=2){
        if(i == A.size()-1) return A[i];
        if(A[i] != A[i+1]) return A[i];
    }
}