Strong Root

codility - Fish 정답 및 해설

뿌리튼튼 CS/Algorithm2017. 8. 8. 21:06

난이도 ★★★☆☆


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





문제 요약

 최종적으로 몇 마리의 물고기가 살아남는지 리턴하기


 1. A.length 가 물고기의 숫자이다.

 2. index 가 각 물고기 번호인데, index 가 작을수록 강의 상류에 있다.

 3. A[index] 는 각 물고기의 크기이며, 큰 녀석이 작은 녀석을 만나면 잡아먹는다.

 4. B[index] 는 각 물고기의 방향이며, 0 은 상류로 가는 방향, 1 은 하류로 가는 방향이다.

 5. 모든 물고기의 속도는 같다. (즉, 같은 방향끼리는 못 만난다)





힌트

 Stack 을 써야한다. 왜 써야하는지 깨달으면 절반 이상은 푼 것이다.

 (B[index] == 1 인 녀석들을 Stack 에 넣자)





이하는 코드입니다.


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
public int solution(int[] A, int[] B) {
    int aliveCount = 0;
    Stack<Integer> downFishes = new Stack<>();
    
    for (int i = 0; i < A.length; i++) {
        if (B[i] == 0) {    // up fish
            aliveCount++;
            
            if (downFishes.isEmpty()) {
                continue;
            }
            
            int downFish = downFishes.peek();
            
            while (true) {
                aliveCount--;
                
                if (A[downFish] < A[i]) {
                    downFishes.pop();
                    
                    if (downFishes.isEmpty()) {
                        break;
                    }
                    
                    downFish = downFishes.peek();
                }
                else {
                    break;
                }
            }
        }
        else {    // down fish
            downFishes.add(i);
            aliveCount++;
        }
    }
    
    return aliveCount;
}
cs

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

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

프로그래머스 완주하지 못한 선수(participant) 정답 코드  (0) 2019.04.15
프로그래머스 팰린드롬(Palindrome) 정답 코드  (0) 2018.06.11
codility - Brackets 정답 및 해설  (0) 2017.08.08
알고리즘의 복잡도란? (3. 빅오 표기법)  (0) 2017.07.28
알고리즘의 복잡도란? (2. 시간 복잡도)  (0) 2017.07.28

codility - Brackets 정답 및 해설

뿌리튼튼 CS/Algorithm2017. 8. 8. 20:00

난이도 ★★☆☆☆


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





문제 요약

 괄호의 짝이 정상적으로 맞는지를 리턴. 단, 빈 문자열 입력시에도 정상이라고 리턴할 것





힌트

 Stack 을 이용하는 전형적인 문제


 1. 여는 괄호 (, {, [ 는 push

 2. 닫는 괄호 ), }, ] 는 pop

 3. stack 이 비어있을 때 pop 하면 에러 발생함. 주의할 것





이하는 코드입니다.


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
public int solution(String S) {
    Stack<Character> stack = new Stack<>();
    
    for (int i = 0; i < S.length(); i++) {
        char c = S.charAt(i);
        
        if (c == '(' || c == '{' || c == '[') {
            stack.push(c);
        }
        else {
            if (stack.isEmpty()) {
                return 0;
            }
            
            char lastC = stack.pop();
            
            if (c == ')' && lastC != '(') {
                return 0;
            }
            
            if (c == '}' && lastC != '{') {
                return 0;
            }
            
            if (c == ']' && lastC != '[') {
                return 0;
            }
        }
    }
    
    if (!stack.isEmpty()) {
        return 0;
    }
    
    return 1;
}
cs

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

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

프로그래머스 팰린드롬(Palindrome) 정답 코드  (0) 2018.06.11
codility - Fish 정답 및 해설  (0) 2017.08.08
알고리즘의 복잡도란? (3. 빅오 표기법)  (0) 2017.07.28
알고리즘의 복잡도란? (2. 시간 복잡도)  (0) 2017.07.28
알고리즘의 복잡도란? (1. 공간 복잡도)  (0) 2017.07.28

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

티스토리툴바