Strong Root

codility - Triangle 정답 및 해설

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

난이도 ★★☆☆☆


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





문제 요약

 입력받은 숫자들을 변의 길이라고 가정했을 때, 삼각형을 그릴 수 있는지를 리턴





힌트

 논리적인 답은 몇줄이면 끝난다. 근데 -.-; 두가지 이유때문에 코드가 지저분해진다. (경우의 수 문제)


 1. 음수가 입력될 수 있다.

 2. 오버플로우를 고려해야 한다.





이하는 코드입니다.


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
public int solution(int[] A) {
    Arrays.sort(A);
 
    for (int i = A.length - 3; i >= 0; i--) {
        if (isTriangular(A[i], A[i + 1], A[i + 2])) {
            return 1;
        }
    }
 
    return 0;
}
 
private boolean isTriangular(int l1, int l2, int l3) {
    boolean ok;
 
    int sum12 = l1 + l2;
    if (l1 > 0 && l2 > 0 && sum12 < 0) {
        ok = true;
    }
    else if (l1 < 0 && l2 < 0 && sum12 > 0) {
        ok = false;
    }
    else {
        ok = sum12 > l3;
    }
 
    if (!ok) {
        return false;
    }
 
    int sum23 = l2 + l3;
    if (l2 > 0 && l3 > 0 && sum23 < 0) {
        ok = true;
    }
    else if (l2 < 0 && l3 < 0 && sum23 > 0) {
        ok = false;
    }
    else {
        ok = sum23 > l1;
    }
 
    if (!ok) {
        return false;
    }
 
    int sum31 = l3 + l1;
    if (l3 > 0 && l1 > 0 && sum31 < 0) {
        ok = true;
    }
    else if (l3 < 0 && l1 < 0 && sum31 > 0) {
        ok = false;
    }
    else {
        ok = sum31 > l2;
    }
 
    return ok;
}
cs

저작자표시 비영리 동일조건

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

알고리즘의 복잡도란? (2. 시간 복잡도)  (0) 2017.07.28
알고리즘의 복잡도란? (1. 공간 복잡도)  (0) 2017.07.28
codility - MaxProductOfThree 정답 및 해설  (0) 2017.07.12
codility - Distinct 정답 및 해설  (0) 2017.07.12
codility - MinAvgTwoSlice 정답 및 해설  (0) 2017.06.09

codility - MaxProductOfThree 정답 및 해설

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

난이도 ★☆☆☆☆


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





문제 요약

 입력받은 숫자들 중 3개를 뽑아서 곱했을 때 가장 큰 값을 리턴





힌트

 정렬을 한 후 최대값끼리 곱한다. 단! 음수에 주의하여야 한다 (경우의 수 문제)





이하는 코드입니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int solution(int[] A) {
    Arrays.sort(A);
 
    if (A[A.length - 1] < 0) {
        return A[A.length - 1] * A[A.length - 2] * A[A.length - 3];
    }
 
    if (A[A.length - 2] < 0 || A[A.length - 3] < 0) {
        return A[A.length - 1] * A[0] * A[1];
    }
 
    int p1 = A[A.length - 1] * A[A.length - 2] * A[A.length - 3];
    int p2 = A[A.length - 1] * A[0] * A[1];
 
    return p1 > p2 ? p1 : p2;
}
cs

저작자표시 비영리 동일조건

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

알고리즘의 복잡도란? (1. 공간 복잡도)  (0) 2017.07.28
codility - Triangle 정답 및 해설  (0) 2017.07.12
codility - Distinct 정답 및 해설  (0) 2017.07.12
codility - MinAvgTwoSlice 정답 및 해설  (0) 2017.06.09
codility - GenomicRangeQuery 정답 및 해설  (0) 2017.06.09

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

codility - CountDiv 정답 및 해설

뿌리튼튼 CS/Algorithm2017. 6. 8. 23:50

난이도 ★★☆☆☆


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





문제 요약

 A와 B사이에서 K로 나누어 떨어지는 수가 몇개인지 찾기





힌트

 수학 문제입니다. 고딩 때 수열 문제 풀듯이 종이에 써서 규칙을 찾아보세요





이하는 코드입니다.


1
2
3
public int solution(int A, int B, int K) {
    return (int) Math.ceil((B - A + 1 - (K - (A % K)) % K) / (double) K);
}
cs

저작자표시 비영리 동일조건

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

codility - GenomicRangeQuery 정답 및 해설  (0) 2017.06.09
codility - PassingCars 정답 및 해설  (0) 2017.06.09
codility - MaxCounters 정답 및 해설  (0) 2017.06.06
codility - MissingInteger 정답 및 해설  (1) 2017.06.06
codility - FrogRiverOne 정답 및 해설  (0) 2017.06.06

codility - MaxCounters 정답 및 해설

뿌리튼튼 CS/Algorithm2017. 6. 6. 23:26

난이도 ★★★★☆


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





문제 요약

 명령어 배열(A)을 실행한 결과 리턴하기





힌트

 Max Counter 명령어(N+1) 를 효율적으로 수행하는 것이 핵심입니다.


 그때그때 실행하지 않고, 모든 결과 수행 후 마지막에 딱 1번만 실행하는 아이디어 적용





이하는 코드입니다.


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
public int[] solution(int N, int[] A) {
    int[] counter = new int[N];
    int tmpMaxCounter = 0;
    int doneMaxCounter = 0;
 
    for (int i = 0; i < A.length; i++) {
        if (A[i] > N) {
            doneMaxCounter = tmpMaxCounter;
        }
        else {
            if (counter[A[i] - 1] < doneMaxCounter) {
                counter[A[i] - 1] = doneMaxCounter;
            }
 
            counter[A[i] - 1]++;
 
            if (counter[A[i] - 1] > tmpMaxCounter) {
                tmpMaxCounter = counter[A[i] - 1];
            }
        }
    }
 
    if (doneMaxCounter > 0) {
        for (int i = 0; i < counter.length; i++) {
            if (counter[i] < doneMaxCounter) {
                counter[i] = doneMaxCounter;
            }
        }
    }
 
    return counter;
}
cs

저작자표시 비영리 동일조건

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

codility - PassingCars 정답 및 해설  (0) 2017.06.09
codility - CountDiv 정답 및 해설  (0) 2017.06.08
codility - MissingInteger 정답 및 해설  (1) 2017.06.06
codility - FrogRiverOne 정답 및 해설  (0) 2017.06.06
codility - PermCheck 정답 및 해설  (0) 2017.06.06

티스토리툴바