코딩테스트 준비하기 - (4) Prefix Sums
 게시 됨 업데이트 됨개발자 공부 / 코딩테스트7분안에 읽기 (약 999 단어)

코딩테스트 준비하기 - (4) Prefix Sums

prefix sum은 부분합 배열을 의미한다. 개념은 단순하다

  1. 다음과 같은 배열 A가 있다.

    A = [ 1, 4, 6, 3, 7, 9 ]

  2. 이때 배열 A의 prefix sum, 즉 부분합 배열 K는 아래와 같다

K = [ 1, 5, 11, 14, 21, 30 ]

상당히 간단한 개념이다. 고등학교 수학시간에 배웠던 것 같은데. 여튼 prefix sum의 장점은 구간의 부분합을 쉽게 구할 수 있다는 점이다.

즉, A[3] + A[4] + A[5] = K[5] - K[2]이다.

Question 1 - CountDiv

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Write a function:

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

that, given three integers A, B and K, returns the number of integers within the range [A..B] that are divisible by K, i.e.:

{ i : A ≤ i ≤ B, i mod K = 0 }

For example, for A = 6, B = 11 and K = 2, your function should return 3, because there are three numbers divisible by 2 within the range [6..11], namely 6, 8 and 10.

Write an efficient algorithm for the following assumptions:

A and B are integers within the range [0..2,000,000,000];
K is an integer within the range [1..2,000,000,000];
A ≤ B.
  • 주어진 A와 B 사이의 숫자들 중 K로 나누어질 수 있는 수의 개수를 반환하라.
  • 나누어 떨어진다의 기준이 X%K == 0 인것이 함정. 0%K == 0이므로 A,B가 0인 경우에 대한 예외처리가 필요했다.
  • 엄청 간단하다고 생각했는데 내가 늘 그렇듯 자꾸 대충짜서 내니깐 edge case에서 예외가 많이 걸림…
  • Codility는 테스트 케이스를 너무 조금준다ㅠㅠ 예외경우도 생각하는게 물론 개발자의 역량이라지만 코딩보다 테스트가 오래걸려서 답답한걸 어카나요..^^ㅠ

My Solution(100%)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 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(int A, int B, int K) {
    // write your code in C++14 (g++ 6.2.0)
    int ret = 0;
    if(A==0){
        if(B==0) return 1;
        if(B==K) return 2;
        if(B<K) return 1;
        ret += 1;
    }
    
    int Adivisible = (A==0) ? 0 : (A-1) / K;
    int Bdivisible = B / K;
    
    if(A==B && B%K==0) return 1;
    
    return ret + (Bdivisible - Adivisible);
}
  • 지금 풀고나니 생각나네 아… 이걸 그냥 부분합으로 풀걸;;;; 개멍청쓰;;

Question 2 - MinDnaSequence

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
A DNA sequence can be represented as a string consisting of the letters A, C, G and T, which correspond to the types of successive nucleotides in the sequence. Each nucleotide has an impact factor, which is an integer. Nucleotides of types A, C, G and T have impact factors of 1, 2, 3 and 4, respectively. You are going to answer several queries of the form: What is the minimal impact factor of nucleotides contained in a particular part of the given DNA sequence?

The DNA sequence is given as a non-empty string S = S[0]S[1]...S[N-1] consisting of N characters. There are M queries, which are given in non-empty arrays P and Q, each consisting of M integers. The K-th query (0 ≤ K < M) requires you to find the minimal impact factor of nucleotides contained in the DNA sequence between positions P[K] and Q[K] (inclusive).

For example, consider string S = CAGCCTA and arrays P, Q such that:

    P[0] = 2    Q[0] = 4
    P[1] = 5    Q[1] = 5
    P[2] = 0    Q[2] = 6
The answers to these M = 3 queries are as follows:

The part of the DNA between positions 2 and 4 contains nucleotides G and C (twice), whose impact factors are 3 and 2 respectively, so the answer is 2.
The part between positions 5 and 5 contains a single nucleotide T, whose impact factor is 4, so the answer is 4.
The part between positions 0 and 6 (the whole string) contains all nucleotides, in particular nucleotide A whose impact factor is 1, so the answer is 1.
Write a function:

class Solution { public int[] solution(String S, int[] P, int[] Q); }

that, given a non-empty string S consisting of N characters and two non-empty arrays P and Q consisting of M integers, returns an array consisting of M integers specifying the consecutive answers to all queries.

Result array should be returned as an array of integers.

For example, given the string S = CAGCCTA and arrays P, Q such that:

    P[0] = 2    Q[0] = 4
    P[1] = 5    Q[1] = 5
    P[2] = 0    Q[2] = 6
the function should return the values [2, 4, 1], as explained above.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..100,000];
M is an integer within the range [1..50,000];
each element of arrays P, Q is an integer within the range [0..N − 1];
P[K] ≤ Q[K], where 0 ≤ K < M;
string S consists only of upper-case English letters A, C, G, T.
  • 문제가 엄청길다ㅜㅠ
  • Nucleotide는 총 4가지가 있다. 각각은 정수값 impact factor과 매칭된다.
    • A:1, C:2, G:3, T:4
  • N개의 문자열로 이뤄진 DNA sequence가 있다.
  • 길이 M의 non-empty array P, Q 가 있다.
  • Query K는 다음을 의미한다
    • DNA sequence의 P[K]와 Q[K] 위치 사이의 minical impact factor를 찾아라

My Solution(67%)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;

vector<int> solution(string &S, vector<int> &P, vector<int> &Q) {
    // write your code in C++14 (g++ 6.2.0)
    // nucleotide A, C, G, T의 DNA Sequence idx별 등장횟수
    int count[4][55555];
    // nucleotide의 impact factor
    map<char, int> impFac = {{'A', 0},{'C', 1},{'G', 2},{'T', 3}};
    
    for(int i=0; i<S.length(); i++){
        char dnaChar = S.at(i);
        int impactFactIdx = impFac[dnaChar];
        
        // 모든 문자의 등장횟수는 기본적으로 이전 등장횟수
        count[0][i] = (i==0) ? 0 : count[0][i-1];
        count[1][i] = (i==0) ? 0 : count[1][i-1];
        count[2][i] = (i==0) ? 0 : count[2][i-1];
        count[3][i] = (i==0) ? 0 : count[3][i-1];
        
        // 등장한 문자의 횟수 +1
        count[impactFactIdx][i] = (i==0) ? count[impactFactIdx][0]+1 : count[impactFactIdx][i-1]+1;
    }
    
    vector<int> ret;
    for(int i=0; i<P.size(); i++){
        int queryStartIdx = P[i]-1;
        int queryEndIdx = Q[i];
        int parDiff[4] = {0};
        
        for(int j=0; j<4; j++){
            parDiff[j] = queryStartIdx<0 ? count[j][queryEndIdx] : count[j][queryEndIdx] - count[j][queryStartIdx];
        }
        for(int j=0; j<4; j++){
            if(parDiff[j]>0){
                ret.push_back(j+1);
                break;
            }
        }
    }
    return ret;
}
  • 로직은 얼추 맞는듯 한데 large dataset에서 런타임 에러가 발생한다. push_back이 너무 느린건가..

Question 2 - MinAvgTwoSlice

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
A non-empty array A consisting of N integers is given. A pair of integers (P, Q), such that 0 ≤ P < Q < N, is called a slice of array A (notice that the slice contains at least two elements). The average of a slice (P, Q) is the sum of A[P] + A[P + 1] + ... + A[Q] divided by the length of the slice. To be precise, the average equals (A[P] + A[P + 1] + ... + A[Q]) / (Q − P + 1).

For example, array A such that:

    A[0] = 4
    A[1] = 2
    A[2] = 2
    A[3] = 5
    A[4] = 1
    A[5] = 5
    A[6] = 8
contains the following example slices:

slice (1, 2), whose average is (2 + 2) / 2 = 2;
slice (3, 4), whose average is (5 + 1) / 2 = 3;
slice (1, 4), whose average is (2 + 2 + 5 + 1) / 4 = 2.5.
The goal is to find the starting position of a slice whose average is minimal.

Write a function:

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

that, given a non-empty array A consisting of N integers, returns the starting position of the slice with the minimal average. If there is more than one slice with a minimal average, you should return the smallest starting position of such a slice.

For example, given array A such that:

    A[0] = 4
    A[1] = 2
    A[2] = 2
    A[3] = 5
    A[4] = 1
    A[5] = 5
    A[6] = 8
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 [−10,000..10,000].

My Solution(60%)

  • memset 사용시에는 string.h 헤더 포함해야 한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <string.h>
using namespace std;
int solution(vector<int> &A) {
    
    int N = A.size(); // 배열 A의 길이
    int parSum[N+1]; // 부분합 배열
    memset(parSum, 0, sizeof(int)*(N+1));
    
    // 배열 A의 부분합을 구한다.
    for(int i=0; i<N; i++){
        parSum[i+1] = parSum[i] + A[i];
    }
    
    // 각 부분합에 대해 평균을 구한다. 동시에 부분합의 평균이 최소가 인덱스를 구한다.
    double min = 111111;
    int minIdx = 0;
    for(int p=0; p<N; p++){
        for(int q=p+1; q<N; q++){
            double diff = parSum[q+1] - parSum[p];
            double avg = diff / (q-p+1);
            if(avg < min){
                min = avg;
                minIdx = p;
            }
        }
    }
    return minIdx;
}
  • 아이디어가 안떠올라서 일단 가장 간단하게 구현한 코드..ㅠ O(N^2 / 2) 이므로 당연하게도 timeout error가 났다.
  • 구글신의 힘을 빌렸다. 아주 그냥 수학문제다 머리아파;;
    : https://nukeguys.tistory.com/175

Question 3 - 괄호변환

  • 디스크 겹치는거 풀다가 도저히 머리가 이해를 못해서 카카오 신입채용 문제로 급선회
  • 익숙한 dfs문제이다.
  • stack의 top()연산은 stack이 비어있으면 Segmentation fault에러가 발생한다.

My Solution(100%)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <string>
#include <vector>
#include <stack>
using namespace std;

string flip(string u){
    // 첫번째와 마지막 문자를 제거한다.
    string parU = u.substr(1, u.length()-2);
    
    // 괄호방향을 뒤집는다.
    string ret = "";
    for(int i=0; i<parU.length(); i++){
        if(parU.at(i) == '(') ret += ")";
        else if(parU.at(i) == ')') ret += "(";
    }
    
    return ret;
}

bool isCorrect(string s){
    stack<char> st;
    for(int i=0; i<s.length(); i++){
        char c = s.at(i);
        if(c == '('){
            st.push(c);
        }
        if(c == ')'){
            if(!st.empty() && st.top() == '(') st.pop();
            else st.push(c);
        }
    }
    if(st.size() > 0) return false;
    else return true;
}

string solve(string p){
    if(p.length() <= 0) return p;
    
    int wIdx = p.length()-1;
    int st = 0;
    for(int i=0; i<p.length(); i++){
        char c = p.at(i);
        if(c == '('){
            st += 1;
        }
        else if(c == ')'){
            st -= 1;
        }
        
        if(st == 0){ // 균형잡힌 문자열 u를 얻음
            wIdx = i;
            break;
        }
    }
    string u = p.substr(0, wIdx+1);
    string v = (wIdx == p.length()-1) ? "" : solve(p.substr(wIdx + 1, p.length()-1-wIdx));
    
    if(isCorrect(u)){ // u가 올바른 문자열인 경우
        return u+v;
    }
    else { // u가 올바른 문자열이 아닌 경우
        string newU = "(";
        newU += v;
        newU += ")";
        newU += flip(u);
        return newU;
    }
}

string solution(string p) {
    string answer = solve(p);
    
    return answer;
}
#

댓글

카탈로그

카테고리

태그

Attention3
ES2015+1
ES61
GA2
Google Analytics2
Hexo1
Keras1
RNN4
YAMLException1
api_server1
change permission1
codility8
coding rule2
coding test8
dacon1
data analysis1
developer8
express1
folder permission1
githubpage2
hexo2
inflearn1
javascript6
jsp1
kaggle1
linear regression2
logistic regression1
mac1
nodejs1
numpy2
nuxtjs2
python2
pytorch10
style guide2
tensorflow9
tensorflow 2.01
tensorflow developer certification7
torchtext1
vue2
vuejs4
vueschool.io2
구글2
구글애널리틱스2
그래프 시각화1
데이콘1
데이터분석1
딥러닝9
딥러닝기초7
로지스틱 회귀1
선형회귀2
순환신경망3
언어모델8
인공지능8
자격증7
자연어 전처리2
자연어처리17
캐글1
케라스3
한국어 임베딩6
×