Strong Root

codility - Distinct 정답 및 해설

뿌리튼튼 CS/Algorithm2017. 7. 12. 14:17

난이도 ★☆☆☆☆


문제를 보시려면 여기를 클릭





문제 요약

 몇 가지 종류의 숫자를 입력받았는지를 리턴





힌트

 자료구조 문제입니다. HashSet 활용하면 끝





이하는 코드입니다.


1
2
3
4
5
6
7
8
9
public int solution(int[] A) {
    Set<Integer> nums = new HashSet<>();
 
    for (int a : A) {
        nums.add(a);
    }
 
    return nums.size();
}
cs

저작자표시 비영리 동일조건 (새창열림)

'뿌리튼튼 CS > Algorithm' 카테고리의 다른 글

codility - Triangle 정답 및 해설  (0) 2017.07.12
codility - MaxProductOfThree 정답 및 해설  (0) 2017.07.12
codility - MinAvgTwoSlice 정답 및 해설  (0) 2017.06.09
codility - GenomicRangeQuery 정답 및 해설  (0) 2017.06.09
codility - PassingCars 정답 및 해설  (0) 2017.06.09

codility - MinAvgTwoSlice 정답 및 해설

뿌리튼튼 CS/Algorithm2017. 6. 9. 00:43

난이도 ★★★☆☆


문제를 보시려면 여기를 클릭





문제 요약

 A배열을 slice한 자식배열 중 평균값이 최저인 경우를 찾고 그때의 시작 인덱스를 리턴하기





힌트

 경우의수 혹은 아이디어 문제입니다. 평균값이 최저인 경우는 딱 2가지씩만 체크하면 됩니다


 풀이법 링크 : http://disq.us/p/1dwms28





이하는 코드입니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int solution(int[] A) {
    double minAvg = (A[0] + A[1]) / 2.0;
    int minStartIndex = 0;
 
    for (int i = 2; i < A.length; i++) {
        double avg = (A[i - 2] + A[i - 1] + A[i]) / 3.0;
 
        if (avg < minAvg) {
            minAvg = avg;
            minStartIndex = i - 2;
        }
 
        avg = (A[i - 1] + A[i]) / 2.0;
 
        if (avg < minAvg) {
            minAvg = avg;
            minStartIndex = i - 1;
        }
    }
 
    return minStartIndex;
}
cs

저작자표시 비영리 동일조건 (새창열림)

'뿌리튼튼 CS > Algorithm' 카테고리의 다른 글

codility - MaxProductOfThree 정답 및 해설  (0) 2017.07.12
codility - Distinct 정답 및 해설  (0) 2017.07.12
codility - GenomicRangeQuery 정답 및 해설  (0) 2017.06.09
codility - PassingCars 정답 및 해설  (0) 2017.06.09
codility - CountDiv 정답 및 해설  (0) 2017.06.08

codility - GenomicRangeQuery 정답 및 해설

뿌리튼튼 CS/Algorithm2017. 6. 9. 00:29

난이도 ★★★★☆


문제를 보시려면 여기를 클릭





문제 요약

 S는 문자열 데이터이고, P와 Q는 인덱스입니다.


 S문자열의 P인덱스부터 Q인덱스까지의 글자 중 가장 작은 글자 찾기





힌트

 풀이법을 모르면 천재라도 힘든 문제입니다. 고민 많이 해보신 후 정답을 익히시는 것을 추천합니다.


 풀이법 링크 : http://disq.us/p/1ckv0jr





이하는 코드입니다.


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
75
76
77
78
79
80
81
public int[] solution(String S, int[] P, int[] Q) {
    int[] answer = new int[P.length];
 
    int[] A = new int[S.length()];
    int[] C = new int[S.length()];
    int[] G = new int[S.length()];
 
    // index == 0
    {
        char c = S.charAt(0);
 
        if (c == 'A') {
            A[0]++;
        }
        else if (c == 'C') {
            C[0]++;
        }
        else if (c == 'G') {
            G[0]++;
        }
    }
 
    // index > 0
    for (int i = 1; i < S.length(); i++) {
        char c = S.charAt(i);
 
        if (c == 'A') {
            A[i] = A[i - 1] + 1;
            C[i] = C[i - 1];
            G[i] = G[i - 1];
        }
        else if (c == 'C') {
            A[i] = A[i - 1];
            C[i] = C[i - 1] + 1;
            G[i] = G[i - 1];
        }
        else if (c == 'G') {
            A[i] = A[i - 1];
            C[i] = C[i - 1];
            G[i] = G[i - 1] + 1;
        }
        else {
            A[i] = A[i - 1];
            C[i] = C[i - 1];
            G[i] = G[i - 1];
        }
    }
 
    for (int i = 0; i < P.length; i++) {
        if (P[i] > 0) {
            if (A[Q[i]] > A[P[i] - 1]) {
                answer[i] = 1;
            }
            else if (C[Q[i]] > C[P[i] - 1]) {
                answer[i] = 2;
            }
            else if (G[Q[i]] > G[P[i] - 1]) {
                answer[i] = 3;
            }
            else {
                answer[i] = 4;
            }
        }
        else {
            if (A[Q[i]] > 0) {
                answer[i] = 1;
            }
            else if (C[Q[i]] > 0) {
                answer[i] = 2;
            }
            else if (G[Q[i]] > 0) {
                answer[i] = 3;
            }
            else {
                answer[i] = 4;
            }
        }
    }
 
    return answer;
}
cs

저작자표시 비영리 동일조건 (새창열림)

'뿌리튼튼 CS > Algorithm' 카테고리의 다른 글

codility - Distinct 정답 및 해설  (0) 2017.07.12
codility - MinAvgTwoSlice 정답 및 해설  (0) 2017.06.09
codility - PassingCars 정답 및 해설  (0) 2017.06.09
codility - CountDiv 정답 및 해설  (0) 2017.06.08
codility - MaxCounters 정답 및 해설  (0) 2017.06.06

codility - PassingCars 정답 및 해설

뿌리튼튼 CS/Algorithm2017. 6. 9. 00:07

난이도 ★★☆☆☆


문제를 보시려면 여기를 클릭





문제 요약

 각 0의 뒤에 나오는 1의 개수를 각각 구한다음 걔네를 다 더하기 (오버플로우나면 -1 리턴)





힌트

 미리 1의 개수를 구해놓는 방법을 통해 중첩for문 제거





이하는 코드입니다. (복잡도 2n의 코드인데, 개선하면 n도 가능할겁니다)


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
public int solution(int[] A) {
    int firstZeroIndex = -1;
 
    for (int i = 0; i < A.length; i++) {
        if (A[i] == 0) {
            firstZeroIndex = i;
            break;
        }
    }
 
    if (firstZeroIndex == -1) {
        return 0;
    }
 
    int totalOneCount = 0;
 
    for (int i = firstZeroIndex + 1; i < A.length; i++) {
        if (A[i] == 1) {
            totalOneCount++;
        }
    }
 
    if (totalOneCount == 0) {
        return 0;
    }
 
    int result = totalOneCount;
    int lastOneCount = 0;
 
    for (int i = firstZeroIndex + 1; i < A.length; i++) {
        if (A[i] == 0) {
            result += totalOneCount - lastOneCount;
 
            if (result > 100000000 || result < 0) {
                return -1;
            }
        }
        else if (A[i] == 1) {
            lastOneCount++;
        }
    }
 
    return result;
}
cs


저작자표시 비영리 동일조건 (새창열림)

'뿌리튼튼 CS > Algorithm' 카테고리의 다른 글

codility - MinAvgTwoSlice 정답 및 해설  (0) 2017.06.09
codility - GenomicRangeQuery 정답 및 해설  (0) 2017.06.09
codility - CountDiv 정답 및 해설  (0) 2017.06.08
codility - MaxCounters 정답 및 해설  (0) 2017.06.06
codility - MissingInteger 정답 및 해설  (1) 2017.06.06

티스토리툴바