코딩테스트 준비하기 - (2) Time complexity

Lesson 3은 시간복잡도에 관한 예제들이다. 총 3문제!

Question1 - FrogJmp

A small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to a position greater than or equal to Y. The small frog always jumps a fixed distance, D.

Count the minimal number of jumps that the small frog must perform to reach its target.

Write a function:

class Solution { public int solution(int X, int Y, int D); }

that, given three integers X, Y and D, returns the minimal number of jumps from position X to a position equal to or greater than Y.

For example, given:

  X = 10
  Y = 85
  D = 30
the function should return 3, because the frog will be positioned as follows:

after the first jump, at position 10 + 30 = 40
after the second jump, at position 10 + 30 + 30 = 70
after the third jump, at position 10 + 30 + 30 + 30 = 100
Write an efficient algorithm for the following assumptions:

X, Y and D are integers within the range [1..1,000,000,000];
X ≤ Y.

• 한번에 D씩 움직이는 개구리가 X에서 Y로 가기위해 몇번 점프해야할까?

My Solution

int solution(int X, int Y, int D) {
    // write your code in C++14 (g++ 6.2.0)
    int gap = Y - X;
    int remainder = gap % D;
    int jump = gap / D;

    if(gap == 0) return 0;
    if(remainder == 0) return jump;
    else return jump+1;
}

Question2 - PermMissingElem

An array A consisting of N different integers is given. The array contains integers in the range [1..(N + 1)], which means that exactly one element is missing.

Your goal is to find that missing element.

Write a function:

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

that, given an array A, returns the value of the missing element.

For example, given array A such that:

  A[0] = 2
  A[1] = 3
  A[2] = 1
  A[3] = 5
the function should return 4, as it is the missing element.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [0..100,000];
the elements of A are all distinct;
each element of array A is an integer within the range [1..(N + 1)].

• N개의 서로다른 정수로 이루어진 배열 A가 주어진다.
• 이 길이 N의 배열 A는 1 ~ N+1 까지의 수로 이뤄진다. 즉, 한개가 빠져있는것.
• 빠진놈을 찾아라

My Solution(50%)

#include <algorithm>

int solution(vector<int> &A) {

    // 받아온 배열 정렬
    sort(A.begin(), A.end());

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

• 왜 이게 50%지? 디버깅이 안되니 불편하다ㅠㅠㅠ 디버깅할 방법을 찾아봐야겠음…

Question3 -

A non-empty array A consisting of N integers is given. Array A represents numbers on a tape.

Any integer P, such that 0 < P < N, splits this tape into two non-empty parts: A[0], A[1], ..., A[P − 1] and A[P], A[P + 1], ..., A[N − 1].

The difference between the two parts is the value of: |(A[0] + A[1] + ... + A[P − 1]) − (A[P] + A[P + 1] + ... + A[N − 1])|

In other words, it is the absolute difference between the sum of the first part and the sum of the second part.

For example, consider array A such that:

  A[0] = 3
  A[1] = 1
  A[2] = 2
  A[3] = 4
  A[4] = 3
We can split this tape in four places:

P = 1, difference = |3 − 10| = 7
P = 2, difference = |4 − 9| = 5
P = 3, difference = |6 − 7| = 1
P = 4, difference = |10 − 3| = 7
Write a function:

int solution(vector<int> &A);

that, given a non-empty array A of N integers, returns the minimal difference that can be achieved.

For example, given:

  A[0] = 3
  A[1] = 1
  A[2] = 2
  A[3] = 4
  A[4] = 3
the function should return 1, as explained above.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [2..100,000];
each element of array A is an integer within the range [−1,000..1,000].

• non-empty array A는 N개의 정수로 이루어짐
• P를 기점으로 배열 A는 0(P-1), P(N-1)의 두개 파트로 나뉜다.
• 각 파트의 합의 차이를 최소로 만드는 P를 찾아서 그 최소값을 반환하라(이때 파트간 합의 차는 절대값 씌운다.)

My Solution(76%)

• 양끝에서 인덱스가 같이 다가오는 아이디어로 풀어봤다.
• 왼쪽집합과 오른쪽 집합의 합을 구해가면서 집합의 차가 작아지는 방향으로 계속 움직이도록 한다.
• 결과는 76점ㅠㅠ 뭘 빼먹은걸까…

// 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 startIdx = 0;
    int endIdx = A.size()-1;
    int sumLeft = A[startIdx];
    int sumRight = A[endIdx];
    
    if(A.size() == 2) return abs(sumLeft - sumRight);
    
    while(true){
        if(sumLeft == sumRight){
            if(endIdx - startIdx == 1){
                return 0;
            }
            else if(endIdx - startIdx == 2){
                return abs(A[startIdx+1]);
            }
            else{
                if(abs(A[startIdx+1] <= abs(A[endIdx-1]))){
                    startIdx++;
                    sumLeft += A[startIdx];
                }
                else{
                    endIdx--;
                    sumRight += A[endIdx];
                }
            }
        }
        // 더 값이 큰 집합을 작아지게 만들거나
        // 더 값이 작은 집합을 커지게 만든다
        else{
            if(startIdx+1 >= endIdx){
                return abs(sumLeft - sumRight);
            }
            int ifMoveRight = abs((sumLeft + A[startIdx+1]) - sumRight);
            int ifMoveLeft = abs(sumLeft - (sumRight + A[endIdx-1]));
            if(ifMoveRight <= ifMoveLeft){
                startIdx++;
                sumLeft += A[startIdx];   
            }
            if(ifMoveRight > ifMoveLeft){
                endIdx--;
                sumRight += A[endIdx];
            }
        }
    }
}

My Solution2(100%)

• 배열을 순회하면서 각 인덱스까지의 합을 저장한다. 반대로도 병렬 수행
• 전체 배열에 대해 두개 배열의 차를 구한다. 최소값을 같이 구한다. 이렇게하면 아마도 O(2N)

int solution(vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)
    int N = A.size();
    vector<int> moveRightBoard(N);
    vector<int> moveLeftBoard(N);
    
    moveRightBoard[0] = A[0];
    moveLeftBoard[N-1] = A[N-1];
    
    if(N == 2) return abs(A[0] - A[1]);
    
    for(int i=1, j=N-2; i<A.size(); i++, j--){
        moveRightBoard[i] = moveRightBoard[i-1] + A[i];
        moveLeftBoard[j] = moveLeftBoard[j+1] + A[j];
    }
    int min = 9999999999999999;
    for(int i=0; i<N-1; i++){
        int diff = abs(moveRightBoard[i] - moveLeftBoard[i+1]);
        if(diff < min){
            min = diff;
        }
    }
    
    return min;
}