코딩테스트 준비하기 - (3) Counting Elements

Codility사이트는 해당 Lessons관련 이론 pdf파일도 같이 제공해준다. pdf 파일이 굉장히 대학시절 알고리즘 교재에서 본것처럼 생겼다.

여튼 생짜로 머리에서 아이디어를 꺼내는 것 보다 이 관련 자료를 읽고 힌트를 얻어 문제를 푸는게 훨씬 유용한 것 같다!!

Counting Elements.pdf

• 그룹 A와 B가 있다. 두 그룹에서 하나의 페어를 찾아 바꿈으로서 각 그룹의 총합이 같도록 만들수 있는지를 판별하려면?
• 각 그룹의 총합의 차를 구한다. 그룹1의 총합이 10, 그룹2의 총합이 13이라고 해보자. 이때

Question1 - FrogRiverOne

A small frog wants to get to the other side of a river. The frog is initially located on one bank of the river (position 0) and wants to get to the opposite bank (position X+1). Leaves fall from a tree onto the surface of the river.

You are given an array A consisting of N integers representing the falling leaves. A[K] represents the position where one leaf falls at time K, measured in seconds.

The goal is to find the earliest time when the frog can jump to the other side of the river. The frog can cross only when leaves appear at every position across the river from 1 to X (that is, we want to find the earliest moment when all the positions from 1 to X are covered by leaves). You may assume that the speed of the current in the river is negligibly small, i.e. the leaves do not change their positions once they fall in the river.

For example, you are given integer X = 5 and array A such that:

  A[0] = 1
  A[1] = 3
  A[2] = 1
  A[3] = 4
  A[4] = 2
  A[5] = 3
  A[6] = 5
  A[7] = 4
In second 6, a leaf falls into position 5. This is the earliest time when leaves appear in every position across the river.

Write a function:

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

that, given a non-empty array A consisting of N integers and integer X, returns the earliest time when the frog can jump to the other side of the river.

If the frog is never able to jump to the other side of the river, the function should return −1.

For example, given X = 5 and array A such that:

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

Write an efficient algorithm for the following assumptions:

N and X are integers within the range [1..100,000];
each element of array A is an integer within the range [1..X].

My Solution(100%)

• 배열초기화 참고
• 1-X까지의 합을 구해두고 counting board에 새로운 정수가 등록될 때마다 현재 sum을 구한다. 현재 sum이 1-X까지의 합과 같아지는 순간이 개구리가 뛸 수 있는 순간.

#include <string.h>
int solution(int X, vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)
    int sum = (1 + X) * X / 2;
    bool countBoard[111111];
    
    memset(countBoard, false, sizeof(bool) * 111111);
    
    int curSum = 0;
    for(int i=0; i<A.size(); i++){
        int k = A[i];
        if(!countBoard[k]){
            // K never occured before
            curSum += k;
            countBoard[k] = true;
            
            if(curSum == sum) return i;
        }
    }
    return -1;
}

Question2 - Max Counters

You are given N counters, initially set to 0, and you have two possible operations on them:

increase(X) − counter X is increased by 1,
max counter − all counters are set to the maximum value of any counter.
A non-empty array A of M integers is given. This array represents consecutive operations:

if A[K] = X, such that 1 ≤ X ≤ N, then operation K is increase(X),
if A[K] = N + 1 then operation K is max counter.
For example, given integer N = 5 and array A such that:

    A[0] = 3
    A[1] = 4
    A[2] = 4
    A[3] = 6
    A[4] = 1
    A[5] = 4
    A[6] = 4
the values of the counters after each consecutive operation will be:

    (0, 0, 1, 0, 0)
    (0, 0, 1, 1, 0)
    (0, 0, 1, 2, 0)
    (2, 2, 2, 2, 2)
    (3, 2, 2, 2, 2)
    (3, 2, 2, 3, 2)
    (3, 2, 2, 4, 2)
The goal is to calculate the value of every counter after all operations.

Write a function:

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

that, given an integer N and a non-empty array A consisting of M integers, returns a sequence of integers representing the values of the counters.

Result array should be returned as an array of integers.

For example, given:

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

Write an efficient algorithm for the following assumptions:

N and M are integers within the range [1..100,000];
each element of array A is an integer within the range [1..N + 1].

• 길이 N의 카운터 배열이 있다(0으로 초기화됨)
• 각 카운터에 대해 어떤 연산을 할지 기준이 되는 연산배열 A가 있다.
• 배열A의 값에 따라 카운터 연산이 달라진다(A의 길이는 M)
  • A[k]의 값 X가 1보다 크거나 같고 N보다 작거나 같다면 counter[X]++
  • A[k]의 값이 N+1과 같다면 counter배열의 모든 값은 현재 카운터 중 최대값으로 변경
• 배열A의 모든 값의 범위는 [1, N+1]
• 연산이 완료된 이후의 카운터 배열을 반환하라.

My Solution1(77%)

• 동적 배열할당시에 new와 delete 키워드를 사용한다.
• 동적배열 할당 및 해제
• int *counter 로 전역변수 선언
• counter = new int[N]() 길이 N의 배열 동적 생성후 0으로 초기화한다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// Max Counter
int *_counter;
vector<int> counter;
int maxCounterVal;

// Max Counter
vector<int> solution(int N, vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)
    
    // 길이 N의 카운터 배열 생성후 0으로 초기화
    // _counter = new int[N]();
    counter.resize(N);
    maxCounterVal = 0;
    
    for(int i=0; i<A.size(); i++){
        int K = A[i];
        if(K == N+1){
            fill(counter.begin(), counter.end(), maxCounterVal);
        }
        else{
            counter[K-1]++;
            if(counter[K-1] > maxCounterVal) maxCounterVal = counter[K-1];
        }
    }
    return counter;
}

• 문제에서 얘기하는 내용을 그대로 정직하게 구현함.
• 값은 제대로 반환하지만 large dataset에서 timeout error가 발생한다.
• 해당 레슨의 핵심이 Counting Elements인 것에 착안해 좀더 고민을 해봤다. 모든 max 연산이 있을때마다 fill을 수행하는 것이 비효율적이다. 최악의 경우 O(N*M)의 성능을 가진 알고리즘.

My Solution2(100%)

#include <vector>
#include <algorithm>
using namespace std;

// Max Counter
vector<int> counter;
int maxCounterVal;

// Max Counter
vector<int> solution(int N, vector<int> &A) {
    // 길이 N의 카운터 배열 생성후 0으로 초기화
    counter.resize(N);
    int prevMax = 0;
    int curMax = 0;
    
    for(int i=0; i<A.size(); i++){
        int whatToDo = A[i];
        if(whatToDo == N+1){
            prevMax = curMax;
            // curMax = 0; // 이부분이 틀렸다.
        }
        else{
            int idx = whatToDo - 1;
            int howOftenAppeared = counter[idx];
            if(howOftenAppeared < prevMax){
                counter[idx] = prevMax+1;
            }
            else{
                counter[idx]++;
            }
            if(counter[idx] > curMax) curMax = counter[idx];
        }
    }
    for(int i=0; i<counter.size(); i++){
        if(counter[i] < prevMax) counter[i] = prevMax;
    }
    return counter;
}

• max변환 연산이 나오면 변환연산 기준max를 저장해둔다.
• max변환 연산이 아닌 경우는 해당 원소의 카운트값(howOftenAppeared)이 변환연산 기준max보다 큰지 작은지를 비교해서 현재의 변환연산 기준max + 1이나 그냥 +1 이렇게 두가지로 연산 분리한다.
• 현재의 max는 계속 업데이트 하다가 변환연산이 나올때마다 변환연산 기준max에 저장해준다.
• 최종적으로 다시 전체 카운터 배열을 순회하면서 변환연산 기준max보다 작은값은 기준max값으로 변환해준다.
• 아 머리아파ㅠ

Question 3 - FindSmallestInteger

This is a demo task.

Write a function:

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

that, given an array A of N integers, returns the smallest positive integer (greater than 0) that does not occur in A.

For example, given A = [1, 3, 6, 4, 1, 2], the function should return 5.

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

Given A = [−1, −3], the function should return 1.

Write an efficient algorithm for the following assumptions:

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

• N개의 정수로 이루어진 배열 A
• A 배열에 없는 가장 작은 정수 X를 찾아라(X>0)

My Solution(100%)

• 아무리 고민해도 그냥 배열 여러번 순회하는 아이디어밖에 떠오르지 않았다. 이경우 시간복잡도가 대충 O(2N)정도 될것같아서.. 그냥 가장 간단하게 풀었다. 의외로 통과

bool counter[1111111] = {false};
bool onePositive = false;
int solution(vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)
    counter[0] = true;
    for(int i=0; i<A.size(); i++){
        int arrVal = A[i];
        if(arrVal <= 0) continue;
        else onePositive = true;
        if(!counter[arrVal]) counter[arrVal] = true;
    }
    
    if(!onePositive) return 1;
    
    for(int i=0; i<1000000; i++){
        if(!counter[i]) return i;
    }
    return 1000000;
}