You are given an array A consisting of N integers.

For each number A[i] such that 0 ≤ i < N, we want to count the number of elements of the array that are not the divisors of A[i]. We say that these elements are non-divisors.

For example, consider integer N = 5 and array A such that:

    A[0] = 3
    A[1] = 1
    A[2] = 2
    A[3] = 3
    A[4] = 6

For the following elements:

A[0] = 3, the non-divisors are: 2, 6, A[1] = 1, the non-divisors are: 3, 2, 3, 6, A[2] = 2, the non-divisors are: 3, 3, 6, A[3] = 3, the non-divisors are: 2, 6, A[4] = 6, there aren't any non-divisors. Write a function:

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

that, given an array A consisting of N integers, returns a sequence of integers representing the amount of non-divisors.

Result array should be returned as an array of integers.

For example, given:

    A[0] = 3
    A[1] = 1
    A[2] = 2
    A[3] = 3
    A[4] = 6

the function should return [2, 4, 3, 2, 0], as explained above.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..50,000]; each element of array A is an integer within the range [1..2 * N].

정수 N개로 구성된 배열 A가 주어집니다.

0 ≤ i < N인 각 숫자 A[i]에 대해, A[i]의 약수가 아닌 배열 요소의 개수를 세고자 합니다. 이러한 요소들을 비약수(non-divisors)라고 합니다.

예를 들어, 정수 N = 5이고 배열 A가 다음과 같다고 가정합니다:

    A[0] = 3
    A[1] = 1
    A[2] = 2
    A[3] = 3
    A[4] = 6

다음 요소들에 대해:

A[0] = 3, 비약수는: 2, 6, A[1] = 1, 비약수는: 3, 2, 3, 6, A[2] = 2, 비약수는: 3, 3, 6, A[3] = 3, 비약수는: 2, 6, A[4] = 6, 비약수가 없습니다.

다음과 같은 함수를 작성하세요:

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

이 함수는 정수 N개로 구성된 배열 A가 주어졌을 때, 비약수의 개수를 나타내는 정수 배열을 반환해야 합니다.

결과 배열은 정수 배열로 반환되어야 합니다.

예를 들어, 다음과 같은 배열 A가 주어졌을 때:

    A[0] = 3
    A[1] = 1
    A[2] = 2
    A[3] = 3
    A[4] = 6

함수는 [2, 4, 3, 2, 0]을 반환해야 합니다.

다음 가정을 위한 효율적인 알고리즘을 작성하세요:

N은 [1…50,000] 범위 내의 정수입니다. 배열 A의 각 요소는 [1…2 * N] 범위 내의 정수입니다.

문제풀이

import java.util.*;

class Solution {
    public int[] solution(int[] A) {
        int N = A.length;
        int[] result = new int[N];
        Map<Integer, Integer> countMap = new HashMap<>();

        for (int num : A) {
            countMap.put(num, countMap.getOrDefault(num, 0) + 1);
        }

        for (int i = 0; i < N; i++) {
            int nonDivisors = N;
            int num = A[i];

            for (int j = 1; j * j <= num; j++) {
                if (num % j == 0) {
                    if (countMap.containsKey(j)) {
                        nonDivisors -= countMap.get(j);
                    }
                    if (j != num / j && countMap.containsKey(num / j)) {
                        nonDivisors -= countMap.get(num / j);
                    }
                }
            }

            result[i] = nonDivisors;
        }

        return result;
    }
}

제출결과

문제풀어보기 -> https://app.codility.com/programmers/lessons/11-sieve_of_eratosthenes/count_non_divisible/

A non-empty array A consisting of N integers is given.

A peak is an array element which is larger than its neighbors. More precisely, it is an index P such that 0 < P < N − 1, A[P − 1] < A[P] and A[P] > A[P + 1].

For example, the following array A:

A[0] = 1
A[1] = 2
A[2] = 3
A[3] = 4
A[4] = 3
A[5] = 4
A[6] = 1
A[7] = 2
A[8] = 3
A[9] = 4
A[10] = 6
A[11] = 2

has exactly three peaks: 3, 5, 10.

We want to divide this array into blocks containing the same number of elements. More precisely, we want to choose a number K that will yield the following blocks:

A[0], A[1], ..., A[K − 1], A[K], A[K + 1], ..., A[2K − 1], ... A[N − K], A[N − K + 1], ..., A[N − 1]. What's more, every block should contain at least one peak. Notice that extreme elements of the blocks (for example A[K − 1] or A[K]) can also be peaks, but only if they have both neighbors (including one in an adjacent blocks).

The goal is to find the maximum number of blocks into which the array A can be divided.

Array A can be divided into blocks as follows:

one block (1, 2, 3, 4, 3, 4, 1, 2, 3, 4, 6, 2). This block contains three peaks. two blocks (1, 2, 3, 4, 3, 4) and (1, 2, 3, 4, 6, 2). Every block has a peak. three blocks (1, 2, 3, 4), (3, 4, 1, 2), (3, 4, 6, 2). Every block has a peak. Notice in particular that the first block (1, 2, 3, 4) has a peak at A[3], because A[2] < A[3] > A[4], even though A[4] is in the adjacent block. However, array A cannot be divided into four blocks, (1, 2, 3), (4, 3, 4), (1, 2, 3) and (4, 6, 2), because the (1, 2, 3) blocks do not contain a peak. Notice in particular that the (4, 3, 4) block contains two peaks: A[3] and A[5].

The maximum number of blocks that array A can be divided into is three.

Write a function:

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

that, given a non-empty array A consisting of N integers, returns the maximum number of blocks into which A can be divided.

If A cannot be divided into some number of blocks, the function should return 0.

For example, given:

A[0] = 1
A[1] = 2
A[2] = 3
A[3] = 4
A[4] = 3
A[5] = 4
A[6] = 1
A[7] = 2
A[8] = 3
A[9] = 4
A[10] = 6
A[11] = 2

the function should return 3, as explained above.

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 [0..1,000,000,000].

비어 있지 않은 정수 배열 A가 주어집니다. 이 배열은 N개의 정수로 구성되어 있습니다.

피크(peak)는 이웃한 요소들보다 큰 배열 요소입니다. 더 정확히 말하면, 피크는 0 < P < N − 1이고 A[P − 1] < A[P] > A[P + 1]인 인덱스 P입니다.

예를 들어, 다음과 같은 배열 A가 있습니다:

A[0] = 1
A[1] = 2
A[2] = 3
A[3] = 4
A[4] = 3
A[5] = 4
A[6] = 1
A[7] = 2
A[8] = 3
A[9] = 4
A[10] = 6
A[11] = 2

이 배열에는 정확히 세 개의 피크가 있습니다: 3, 5, 10.

이 배열을 동일한 수의 요소를 포함하는 블록으로 나누고자 합니다. 더 정확히 말하면, 다음과 같은 블록을 생성할 수 있는 숫자 K를 선택하고자 합니다:

A[0], A[1], …, A[K − 1], A[K], A[K + 1], …, A[2K − 1], … A[N − K], A[N − K + 1], …, A[N − 1].

또한, 각 블록에는 적어도 하나의 피크가 포함되어야 합니다. 블록의 극단 요소(예: A[K − 1] 또는 A[K])도 피크가 될 수 있지만, 이 경우 이웃 요소(인접 블록에 있는 요소 포함)가 있어야 합니다.

목표는 배열 A를 최대한 많은 블록으로 나누는 것입니다.

배열 A는 다음과 같이 블록으로 나눌 수 있습니다:

한 블록 (1, 2, 3, 4, 3, 4, 1, 2, 3, 4, 6, 2). 이 블록에는 세 개의 피크가 포함되어 있습니다. 두 블록 (1, 2, 3, 4, 3, 4) 및 (1, 2, 3, 4, 6, 2). 각 블록에는 피크가 하나씩 포함되어 있습니다. 세 블록 (1, 2, 3, 4), (3, 4, 1, 2), (3, 4, 6, 2). 각 블록에는 피크가 하나씩 포함되어 있습니다. 특히 첫 번째 블록 (1, 2, 3, 4)에는 A[3]에 피크가 있습니다. 이는 A[2] < A[3] > A[4]이기 때문입니다. 비록 A[4]는 인접 블록에 있습니다. 그러나 배열 A는 네 블록 (1, 2, 3), (4, 3, 4), (1, 2, 3) 및 (4, 6, 2)으로 나눌 수 없습니다. 왜냐하면 (1, 2, 3) 블록에는 피크가 포함되어 있지 않기 때문입니다. 특히 (4, 3, 4) 블록에는 두 개의 피크 A[3] 및 A[5]가 포함되어 있습니다.

배열 A를 최대한 많은 블록으로 나눌 수 있는 최대 수는 세 개입니다.

다음 함수를 작성하세요:

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

이 함수는 비어 있지 않은 정수 배열 A가 주어졌을 때, 배열 A를 나눌 수 있는 최대 블록 수를 반환해야 합니다.

배열 A를 일부 블록으로 나눌 수 없는 경우, 함수는 0을 반환해야 합니다.

예를 들어, 다음과 같은 배열 A가 주어졌을 때:

A[0] = 1
A[1] = 2
A[2] = 3
A[3] = 4
A[4] = 3
A[5] = 4
A[6] = 1
A[7] = 2
A[8] = 3
A[9] = 4
A[10] = 6
A[11] = 2

함수는 위에서 설명한 대로 3을 반환해야 합니다.

다음 가정을 위한 효율적인 알고리즘을 작성하세요:

N은 [1…100,000] 범위 내의 정수입니다. 배열 A의 각 요소는 [0…1,000,000,000] 범위 내의 정수입니다.

문제풀이

import java.util.*;

class Solution {
    public int solution(int[] A) {
        int N = A.length;
        if (N < 3) return 0;

        List<Integer> peaks = new ArrayList<>();
        for (int i = 1; i < N - 1; i++) {
            if (A[i] > A[i-1] && A[i] > A[i+1]) {
                peaks.add(i);
            }
        }
        if (peaks.size() == 0) return 0;

        for (int size = 1; size <= N; size++) {
            if (N % size != 0) continue;
            int blockCount = N / size;
            boolean[] blockHasPeak = new boolean[blockCount];
            int peakIndex = 0;

            for (int peak : peaks) {
                int blockIndex = peak / size;
                blockHasPeak[blockIndex] = true;
            }

            boolean allBlocksHavePeak = true;
            for (boolean hasPeak : blockHasPeak) {
                if (!hasPeak) {
                    allBlocksHavePeak = false;
                    break;
                }
            }

            if (allBlocksHavePeak) {
                return blockCount;
            }
        }

        return 0;
    }
}

제출결과

문제풀어보기 -> https://app.codility.com/programmers/lessons/10-prime_and_composite_numbers/peaks/

A non-empty array A consisting of N integers is given.

A peak is an array element which is larger than its neighbours. More precisely, it is an index P such that 0 < P < N − 1 and A[P − 1] < A[P] > A[P + 1].

For example, the following array A:

A[0] = 1
A[1] = 5
A[2] = 3
A[3] = 4
A[4] = 3
A[5] = 4
A[6] = 1
A[7] = 2
A[8] = 3
A[9] = 4
A[10] = 6
A[11] = 2

has exactly four peaks: elements 1, 3, 5 and 10.

You are going on a trip to a range of mountains whose relative heights are represented by array A, as shown in a figure below. You have to choose how many flags you should take with you. The goal is to set the maximum number of flags on the peaks, according to certain rules.

Flags can only be set on peaks. What's more, if you take K flags, then the distance between any two flags should be greater than or equal to K. The distance between indices P and Q is the absolute value |P − Q|.

For example, given the mountain range represented by array A, above, with N = 12, if you take:

two flags, you can set them on peaks 1 and 5; three flags, you can set them on peaks 1, 5 and 10; four flags, you can set only three flags, on peaks 1, 5 and 10. You can therefore set a maximum of three flags in this case.

Write a function:

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

that, given a non-empty array A of N integers, returns the maximum number of flags that can be set on the peaks of the array.

For example, the following array A:

A[0] = 1
A[1] = 5
A[2] = 3
A[3] = 4
A[4] = 3
A[5] = 4
A[6] = 1
A[7] = 2
A[8] = 3
A[9] = 4
A[10] = 6
A[11] = 2

the function should return 3, as explained above.

Write an efficient algorithm for the following assumptions:

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

비어 있지 않은 정수 배열 A가 주어집니다. 이 배열은 N개의 정수로 구성되어 있습니다.

피크(peak)는 이웃한 요소들보다 큰 배열 요소입니다. 더 정확히 말하면, 피크는 0 < P < N − 1이고 A[P − 1] < A[P] > A[P + 1]인 인덱스 P입니다.

예를 들어, 다음과 같은 배열 A가 있습니다:

A[0] = 1
A[1] = 5
A[2] = 3
A[3] = 4
A[4] = 3
A[5] = 4
A[6] = 1
A[7] = 2
A[8] = 3
A[9] = 4
A[10] = 6
A[11] = 2

이 배열에는 정확히 네 개의 피크가 있습니다: 요소 1, 3, 5, 10.

당신은 산맥을 여행할 예정이며, 이 산맥의 상대적인 높이는 배열 A로 나타냅니다. 목표는 피크에 최대한 많은 깃발을 세우는 것입니다. 깃발을 세우는 규칙은 다음과 같습니다: 깃발은 피크에만 세울 수 있습니다. 또한, K개의 깃발을 세우려면 두 깃발 사이의 거리가 K 이상이어야 합니다. 인덱스 P와 Q 사이의 거리는 절대값 |P − Q|입니다.

예를 들어, 주어진 배열 A에서 N = 12일 때:

두 개의 깃발을 세우려면 피크 1과 5에 세울 수 있습니다. 세 개의 깃발을 세우려면 피크 1, 5, 10에 세울 수 있습니다. 네 개의 깃발을 세우려면 피크 1, 5, 10에 세울 수 있습니다. 따라서 이 경우 최대 세 개의 깃발을 세울 수 있습니다.

다음 함수를 작성하세요:

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

이 함수는 비어 있지 않은 정수 배열 A가 주어졌을 때, 배열의 피크에 세울 수 있는 최대 깃발 수를 반환해야 합니다.

예를 들어, 다음과 같은 배열 A가 주어졌을 때:

A[0] = 1
A[1] = 5
A[2] = 3
A[3] = 4
A[4] = 3
A[5] = 4
A[6] = 1
A[7] = 2
A[8] = 3
A[9] = 4
A[10] = 6
A[11] = 2

함수는 위에서 설명한 대로 3을 반환해야 합니다.

다음 가정을 위한 효율적인 알고리즘을 작성하세요:

N은 [1…400,000] 범위 내의 정수입니다. 배열 A의 각 요소는 [0…1,000,000,000] 범위 내의 정수입니다.

문제풀이

import java.util.*;

class Solution {
    public int solution(int[] A) {
        int N = A.length;
        if (N < 3) return 0;

        List<Integer> peaks = new ArrayList<>();
        for (int i = 1; i < N - 1; i++) {
            if (A[i] > A[i-1] && A[i] > A[i+1]) {
                peaks.add(i);
            }
        }
        if (peaks.size() == 0) return 0;

        int left = 1;
        int right = peaks.size();
        int maxFlags = 0;

        while (left <= right) {
            int mid = (left + right) / 2;
            if (canPlaceFlags(peaks, mid)) {
                maxFlags = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return maxFlags;
    }

    private boolean canPlaceFlags(List<Integer> peaks, int k) {
        int flags = 1;
        int lastFlag = peaks.get(0);
        for (int i = 1; i < peaks.size(); i++) {
            if (peaks.get(i) - lastFlag >= k) {
                flags++;
                lastFlag = peaks.get(i);
                if (flags == k) return true;
            }
        }
        return false;
    }
}

제출결과

문제풀어보기 -> https://app.codility.com/programmers/lessons/10-prime_and_composite_numbers/flags/

An integer N is given, representing the area of some rectangle.

The area of a rectangle whose sides are of length A and B is A * B, and the perimeter is 2 * (A + B).

The goal is to find the minimal perimeter of any rectangle whose area equals N. The sides of this rectangle should be only integers.

For example, given integer N = 30, rectangles of area 30 are:

(1, 30), with a perimeter of 62, (2, 15), with a perimeter of 34, (3, 10), with a perimeter of 26, (5, 6), with a perimeter of 22. Write a function:

class Solution { public int solution(int N); }

that, given an integer N, returns the minimal perimeter of any rectangle whose area is exactly equal to N.

For example, given an integer N = 30, the function should return 22, as explained above.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..1,000,000,000].

정수 N이 주어졌을 때, 이는 어떤 직사각형의 넓이를 나타냅니다.

한 변의 길이가 A와 B인 직사각형의 넓이는 A * B이고, 둘레는 2 * (A + B)입니다.

목표는 넓이가 N인 직사각형의 둘레 중 최소값을 찾는 것입니다. 이 직사각형의 변의 길이는 모두 정수여야 합니다.

예를 들어, 주어진 정수 N = 30일 때, 넓이가 30인 직사각형은 다음과 같습니다:

(1, 30), 둘레는 62, (2, 15), 둘레는 34, (3, 10), 둘레는 26, (5, 6), 둘레는 22.

다음과 같은 함수를 작성하세요:

class Solution { 
    public int solution(int N); 
}

이 함수는 정수 N이 주어졌을 때, 넓이가 정확히 N인 직사각형의 최소 둘레를 반환해야 합니다.

예를 들어, 정수 N = 30이 주어졌을 때, 함수는 위에서 설명한 대로 22를 반환해야 합니다.

다음 가정을 위한 효율적인 알고리즘을 작성하세요:

N은 [1…1,000,000,000] 범위 내의 정수입니다.

문제풀이

import java.util.*;

class Solution {
    public int solution(int N) {
        int minPerimeter = Integer.MAX_VALUE;
        for (int i = 1; i * i <= N; i++) {
            if (N % i == 0) {
                int A = i;
                int B = N / i;
                int perimeter = 2 * (A + B);
                minPerimeter = Math.min(minPerimeter, perimeter);
            }
        }
        return minPerimeter;
    }
}

이전문제인 CountFactors와 유사하게 반복문에서 i * i <= N의 범위 지정을 통해 반복문의 반복횟수를 줄여 시간을 단축하였습니다. 왜냐하면 주어진 정수가 직사각형의 넓이이기 때문에 해당 정수의 약수가 한변의 길이 A와 B가 될 수있습니다.

하여 약수에 해당하는 값만 거른뒤 2*(A+B) 한변의길이A와B를 더하고 2를 곱한값 => 둘레를 계산하여 perimeter에 저장하고 이를 비교하여 최소값으로 업데이트합니다.

제출결과

문제풀어보기 -> https://app.codility.com/programmers/lessons/10-prime_and_composite_numbers/min_perimeter_rectangle/

A positive integer D is a factor of a positive integer N if there exists an integer M such that N = D * M.

For example, 6 is a factor of 24, because M = 4 satisfies the above condition (24 = 6 * 4).

Write a function:

class Solution { public int solution(int N); }

that, given a positive integer N, returns the number of its factors.

For example, given N = 24, the function should return 8, because 24 has 8 factors, namely 1, 2, 3, 4, 6, 8, 12, 24. There are no other factors of 24.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..2,147,483,647].

양의 정수 D는 양의 정수 N의 인수입니다. 만약 정수 M이 존재하여 N = D * M을 만족한다면, D는 N의 인수입니다.

예를 들어, 6은 24의 인수입니다. 왜냐하면 M = 4가 위의 조건을 만족하기 때문입니다 (24 = 6 * 4).

다음과 같은 함수를 작성하세요:

class Solution { 
    public int solution(int N); 
}

이 함수는 양의 정수 N이 주어졌을 때, N의 인수의 수를 반환해야 합니다.

예를 들어, N = 24가 주어지면, 함수는 8을 반환해야 합니다. 왜냐하면 24는 8개의 인수(1, 2, 3, 4, 6, 8, 12, 24)를 가지고 있기 때문입니다. 24의 다른 인수는 없습니다.

다음 가정을 위한 효율적인 알고리즘을 작성하세요:

N은 [1…2,147,483,647] 범위 내의 정수입니다.

문제풀이

import java.util.*;

class Solution {
    public int solution(int N) {
        int count = 0;
        if(N == 0){
            return 0;
        }
        for(int i = 1; i <= N; i++){
         if(N % i == 0){
             count++;
         }   
        }
        return count;
    }
}

해당 코드로 제출 시 큰수에서 타임아웃 발생

수정 ->

import java.util.*;

class Solution {
    public int solution(int N) {
        if (N == 0) {
            return 0;
        }
        int count = 0;
        for (int i = 1; i * i <= N; i++) {
            if (N % i == 0) {
                count++;
                if (i != N / i) {
                    count++;
                }
            }
        }
        return count;
    }
}

36의 약수는 1, 2, 3, 4, 6, 9, 12, 18, 36으로 총 9개입니다. 위 규칙에서 1*36 = 36, 2 * 18 = 36, 3 * 12 = 36 이런식으로 규칙을 볼 수 있습니다.

반복문의 예시를 보면 i = 1: 36 % 1 == 0이므로 count++ (count = 1), 1 != 36 / 1이므로 count++ (count = 2)

i = 2: 36 % 2 == 0이므로 count++ (count = 3), 2 != 36 / 2이므로 count++ (count = 4)

i = 3: 36 % 3 == 0이므로 count++ (count = 5), 3 != 36 / 3이므로 count++ (count = 6)

i = 4: 36 % 4 == 0이므로 count++ (count = 7), 4 != 36 / 4이므로 count++ (count = 8)

i = 5: 36 % 5 != 0이므로 count 하지 않음

i = 6: 36 % 6 == 0이므로 count++ (count = 9), 6 == 36 / 6이므로 count 하지 않음

이런식으로 i * i <= N의 범위 지정을 통해 반복문의 반복횟수를 줄여 시간을 단축하고 중복 조건을 제외하고 ex)'6' 카운팅하여 값을 구할 수 있습니다.

제출결과 아직 92% 성능으로 개선이 필요합니다..

문제풀어보기 -> https://app.codility.com/programmers/lessons/10-prime_and_composite_numbers/count_factors/

A non-empty array A consisting of N integers is given.

A triplet (X, Y, Z), such that 0 ≤ X < Y < Z < N, is called a double slice.

The sum of double slice (X, Y, Z) is the total of A[X + 1] + A[X + 2] + ... + A[Y − 1] + A[Y + 1] + A[Y + 2] + ... + A[Z − 1].

For example, array A such that:

A[0] = 3
A[1] = 2
A[2] = 6
A[3] = -1
A[4] = 4
A[5] = 5
A[6] = -1
A[7] = 2

contains the following example double slices:

double slice (0, 3, 6), sum is 2 + 6 + 4 + 5 = 17, double slice (0, 3, 7), sum is 2 + 6 + 4 + 5 − 1 = 16, double slice (3, 4, 5), sum is 0. The goal is to find the maximal sum of any double slice.

Write a function:

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

that, given a non-empty array A consisting of N integers, returns the maximal sum of any double slice.

For example, given:

A[0] = 3
A[1] = 2
A[2] = 6
A[3] = -1
A[4] = 4
A[5] = 5
A[6] = -1
A[7] = 2

the function should return 17, because no double slice of array A has a sum of greater than 17.

Write an efficient algorithm for the following assumptions:

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

비어 있지 않은 N개의 정수로 구성된 배열 A가 주어집니다.

0 ≤ X < Y < Z < N을 만족하는 세 개의 요소 (X, Y, Z)를 더블 슬라이스라고 합니다.

더블 슬라이스 (X, Y, Z)의 합은 A[X + 1] + A[X + 2] + … + A[Y − 1] + A[Y + 1] + A[Y + 2] + … + A[Z − 1]의 총합입니다.

예를 들어, 배열 A가 다음과 같다면:

A[0] = 3
A[1] = 2
A[2] = 6
A[3] = -1
A[4] = 4
A[5] = 5
A[6] = -1
A[7] = 2

다음과 같은 예시 더블 슬라이스가 포함됩니다:

더블 슬라이스 (0, 3, 6), 합은 2 + 6 + 4 + 5 = 17, 더블 슬라이스 (0, 3, 7), 합은 2 + 6 + 4 + 5 − 1 = 16, 더블 슬라이스 (3, 4, 5), 합은 0. 목표는 모든 더블 슬라이스 중 최대 합을 찾는 것입니다.

다음과 같은 함수를 작성하세요:

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

비어 있지 않은 N개의 정수로 구성된 배열 A가 주어지면, 최대 합을 가지는 더블 슬라이스의 합을 반환하는 함수를 작성하세요.

예를 들어, 주어진 배열이 다음과 같다면:

A[0] = 3
A[1] = 2
A[2] = 6
A[3] = -1
A[4] = 4
A[5] = 5
A[6] = -1
A[7] = 2

함수는 17을 반환해야 합니다. 왜냐하면 배열 A의 어떤 더블 슬라이스도 17보다 큰 합을 가지지 않기 때문입니다.

다음 가정을 위한 효율적인 알고리즘을 작성하세요:

N은 [3…100,000] 범위 내의 정수입니다. 배열 A의 각 요소는 [−10,000…10,000] 범위 내의 정수입니다.

문제풀이

class Solution {
    public int solution(int[] A) {
        int N = A.length;
        int[] maxEnd = new int[N];
        int[] maxStart = new int[N];

        for (int i = 1; i < N - 1; i++) {
            maxEnd[i] = Math.max(0, maxEnd[i - 1] + A[i]);
        }

        for (int i = N - 2; i > 0; i--) {
            maxStart[i] = Math.max(0, maxStart[i + 1] + A[i]);
        }

        int maxSlice = 0;
        for (int i = 1; i < N - 1; i++) {
            maxSlice = Math.max(maxSlice, maxEnd[i - 1] + maxStart[i + 1]);
        }
        return maxSlice;
    }
}

2개의 배열을 생성: 끝점부터 중간점 사이의 값의 합을 저장할 배열01 시작점부터 중간점 사이의 값의 합을 저장할 배열02

반복문으로 해당 배열에 계산 값을 저장해줌

ex) A(0,3,6)일 경우 배열01 -> A[1,2]를 더한값을 배열로 저장 배열02 -> A[4,5]를 더한값을 배열로 저장,

배열에 다 저장이 되면

다시 반복문을 통해 지점이 변경되었을때 배열1과 배열2의 합을 maxSlice라는 변수에 담고 Math.max를 통해 해당 값을 업데이트하여 리턴값을 계산

제출결과

문제풀어보기 -> https://app.codility.com/programmers/lessons/9-maximum_slice_problem/max_double_slice_sum/

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. The sum of a slice (P, Q) is the total of A[P] + A[P+1] + ... + A[Q].

Write a function:

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

that, given an array A consisting of N integers, returns the maximum sum of any slice of A.

For example, given array A such that:

A[0] = 3 A[1] = 2 A[2] = -6 A[3] = 4 A[4] = 0 the function should return 5 because:

(3, 4) is a slice of A that has sum 4, (2, 2) is a slice of A that has sum −6, (0, 1) is a slice of A that has sum 5, no other slice of A has sum greater than (0, 1). Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..1,000,000]; each element of array A is an integer within the range [−1,000,000..1,000,000]; the result will be an integer within the range [−2,147,483,648..2,147,483,647].

비어 있지 않은 N개의 정수로 구성된 배열 A가 주어집니다. 0 ≤ P ≤ Q < N인 두 정수 (P, Q) 쌍을 배열 A의 슬라이스라고 합니다. 슬라이스 (P, Q)의 합은 A[P] + A[P+1] + … + A[Q]의 총합입니다.

다음과 같은 함수를 작성하세요:

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

이 함수는 N개의 정수로 구성된 배열 A가 주어졌을 때, 배열 A의 모든 슬라이스 중 최대 합을 반환해야 합니다.

예를 들어, 배열 A가 다음과 같다면:

A[0] = 3 A[1] = 2 A[2] = -6 A[3] = 4 A[4] = 0

함수는 5를 반환해야 합니다. 그 이유는:

(3, 4)는 합이 4인 슬라이스입니다. (2, 2)는 합이 -6인 슬라이스입니다. (0, 1)는 합이 5인 슬라이스입니다. 다른 어떤 슬라이스도 (0, 1)보다 큰 합을 가지지 않습니다. 다음 가정을 만족하는 효율적인 알고리즘을 작성하세요:

N은 [1…1,000,000] 범위 내의 정수입니다. 배열 A의 각 요소는 [-1,000,000…1,000,000] 범위 내의 정수입니다. 결과는 [-2,147,483,648…2,147,483,647] 범위 내의 정수입니다.

문제풀이

import java.util.*;

class Solution {
    public int solution(int[] A) {
        int BigListCheck = A[0];
        int BigList = A[0];
        for(int i = 1; i < A.length; i++){
            BigListCheck = Math.max(A[i], BigListCheck + A[i]);
            BigList = Math.max(BigList, BigListCheck);
        }
        return BigList;
    }
}

Math.max()를 사용하여 A배열을 이전 반복문만큼 더한 것(BigListCheck)과 현재 반복회차의 새로운 A배열의 값이 큰지 체크해고 둘중 큰 값을 BigListCheck의 값에 넣습니다. A[0]=1, A[1]=1, A[2]=3 일 경우 2번째 반복시에 BigListCheck는 3("A[2]") 즉 "3" 1(BigListCheck의 초기값) + 1(A[1]) 즉 "2"를 비교하여 큰값 A[2]를 BigListCheck로 업데이트합니다, 그다음 BigListCheck와 최종 BigList를 비교하여 최종값을 업데이트합니다.

제출결과

문제풀어보기 -> https://app.codility.com/programmers/lessons/9-maximum_slice_problem/max_slice_sum/

An array A consisting of N integers is given. It contains daily prices of a stock share for a period of N consecutive days. If a single share was bought on day P and sold on day Q, where 0 ≤ P ≤ Q < N, then the profit of such transaction is equal to A[Q] − A[P], provided that A[Q] ≥ A[P]. Otherwise, the transaction brings loss of A[P] − A[Q].

For example, consider the following array A consisting of six elements such that:

A[0] = 23171 A[1] = 21011 A[2] = 21123 A[3] = 21366 A[4] = 21013 A[5] = 21367 If a share was bought on day 0 and sold on day 2, a loss of 2048 would occur because A[2] − A[0] = 21123 − 23171 = −2048. If a share was bought on day 4 and sold on day 5, a profit of 354 would occur because A[5] − A[4] = 21367 − 21013 = 354. Maximum possible profit was 356. It would occur if a share was bought on day 1 and sold on day 5.

Write a function,

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

that, given an array A consisting of N integers containing daily prices of a stock share for a period of N consecutive days, returns the maximum possible profit from one transaction during this period. The function should return 0 if it was impossible to gain any profit.

For example, given array A consisting of six elements such that:

A[0] = 23171 A[1] = 21011 A[2] = 21123 A[3] = 21366 A[4] = 21013 A[5] = 21367 the function should return 356, as explained above.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [0..400,000]; each element of array A is an integer within the range [0..200,000].

N개의 정수로 구성된 배열 A가 주어집니다. 이 배열은 N일 동안의 주식 가격을 나타냅니다. 만약 P일에 주식을 사고 Q일에 팔았다면, 여기서 0 ≤ P ≤ Q < N, 그러면 이러한 거래의 이익은 A[Q] − A[P]와 같습니다. 단, A[Q] ≥ A[P]인 경우에만 이익이 발생합니다. 그렇지 않으면 거래는 A[P] − A[Q]만큼의 손실을 가져옵니다.

예를 들어, 다음과 같은 6개의 요소로 구성된 배열 A를 고려해보세요:

A[0] = 23171 A[1] = 21011 A[2] = 21123 A[3] = 21366 A[4] = 21013 A[5] = 21367

만약 0일에 주식을 사고 2일에 팔았다면, A[2] − A[0] = 21123 − 23171 = −2048이므로 2048의 손실이 발생합니다. 만약 4일에 주식을 사고 5일에 팔았다면, A[5] − A[4] = 21367 − 21013 = 354이므로 354의 이익이 발생합니다. 최대 가능한 이익은 356이며, 이는 1일에 주식을 사고 5일에 팔았을 때 발생합니다.

다음과 같은 함수를 작성하세요:

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

N일 동안의 주식 가격을 나타내는 N개의 정수로 구성된 배열 A가 주어졌을 때, 이 기간 동안 한 번의 거래로 얻을 수 있는 최대 이익을 반환하는 함수를 작성하세요. 만약 이익을 얻을 수 없는 경우 함수는 0을 반환해야 합니다.

예를 들어, 다음과 같은 6개의 요소로 구성된 배열 A가 주어졌을 때:

A[0] = 23171 A[1] = 21011 A[2] = 21123 A[3] = 21366 A[4] = 21013 A[5] = 21367

함수는 356을 반환해야 합니다.

다음 가정을 위한 효율적인 알고리즘을 작성하세요:

N은 [0…400,000] 범위 내의 정수입니다. 배열 A의 각 요소는 [0…200,000] 범위 내의 정수입니다.

문제풀이

import java.util.*;

class Solution {
    public int solution(int[] A) {
        if (A.length == 0) {
            return 0; // 배열이 비어 있는 경우
        }

        int minPrice = A[0];
        int maxProfit = 0;

        for (int i = 1; i < A.length; i++) {
            maxProfit = Math.max(maxProfit, A[i] - minPrice);
            minPrice = Math.min(minPrice, A[i]);
        }

        return maxProfit;
    }
}

사용함수 : Math.max(a, b) -> a와 b중 더 큰값을 반환

현재까지의 최대 이익(maxProfit)과 현재 가격에서 최소 가격을 뺀 값(A[i] - minPrice)을 비교하여 더 큰 값을 maxProfit에 저장하고 이를 통해 최대 이익을 업데이트

제출결과

문제풀어보기 -> https://app.codility.com/programmers/lessons/9-maximum_slice_problem/max_profit/

A non-empty array A consisting of N integers is given.

The leader of this array is the value that occurs in more than half of the elements of A.

An equi leader is an index S such that 0 ≤ S < N − 1 and two sequences A[0], A[1], ..., A[S] and A[S + 1], A[S + 2], ..., A[N − 1] have leaders of the same value.

For example, given array A such that:

A[0] = 4
A[1] = 3
A[2] = 4
A[3] = 4
A[4] = 4
A[5] = 2

we can find two equi leaders:

0, because sequences: (4) and (3, 4, 4, 4, 2) have the same leader, whose value is 4. 2, because sequences: (4, 3, 4) and (4, 4, 2) have the same leader, whose value is 4. The goal is to count the number of equi leaders.

Write a function:

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

that, given a non-empty array A consisting of N integers, returns the number of equi leaders.

For example, given:

A[0] = 4
A[1] = 3
A[2] = 4
A[3] = 4
A[4] = 4
A[5] = 2

the function should return 2, as explained above.

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,000..1,000,000,000].

비어 있지 않은 N개의 정수로 구성된 배열 A가 주어집니다.

이 배열의 리더는 A의 요소의 절반 이상에서 발생하는 값입니다.

이퀴 리더는 0 ≤ S < N − 1인 인덱스 S로, 두 시퀀스 A[0], A[1], …, A[S]와 A[S + 1], A[S + 2], …, A[N − 1]이 동일한 값의 리더를 가지는 경우입니다.

예를 들어, 다음과 같은 배열 A가 주어졌을 때:

A[0] = 4
A[1] = 3
A[2] = 4
A[3] = 4
A[4] = 4
A[5] = 2

다음과 같은 두 개의 이퀴 리더를 찾을 수 있습니다:

0, 시퀀스: (4)와 (3, 4, 4, 4, 2)가 동일한 리더 값 4를 가집니다. 2, 시퀀스: (4, 3, 4)와 (4, 4, 2)가 동일한 리더 값 4를 가집니다. 목표는 이퀴 리더의 수를 세는 것입니다.

다음과 같은 함수를 작성하세요:

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

비어 있지 않은 N개의 정수로 구성된 배열 A가 주어졌을 때, 이퀴 리더의 수를 반환하는 함수를 작성하세요.

예를 들어, 다음과 같은 배열이 주어졌을 때:

A[0] = 4
A[1] = 3
A[2] = 4
A[3] = 4
A[4] = 4
A[5] = 2

함수는 위에서 설명한 대로 2를 반환해야 합니다.

다음 가정을 위한 효율적인 알고리즘을 작성하세요:

N은 [1…100,000] 범위 내의 정수입니다. 배열 A의 각 요소는 [−1,000,000,000…1,000,000,000] 범위 내의 정수입니다.

문제풀이

import java.util.*;

class Solution {
    public int solution(int[] A) {
        int N = A.length;
        Map<Integer, Integer> countMap = new HashMap<>();

        int leader = A[0];
        int leaderCount = 0;

        for(int num : A){
            countMap.put(num, countMap.getOrDefault(num, 0) + 1);
            if(countMap.get(num) > leaderCount){
                leader = num;
                leaderCount = countMap.get(num);
            }
        }

        if (leaderCount <= N / 2) { 
            return 0; 
        }

        int equiLeaders = 0;
        int leftLeaderCount = 0;
        int rightLeaderCount = leaderCount;

        for (int i = 0; i < N; i++) {
            if (A[i] == leader) {
                leftLeaderCount++;
                rightLeaderCount--;
            }

            if (leftLeaderCount > (i + 1) / 2 && rightLeaderCount > (N - i - 1) / 2) {
                equiLeaders++;
            }
        }

        return equiLeaders; 
    }
}

우선 배열 A 만큼 반복문을 돌려 리더를 구합니다. 여기서 "countMap.getOrDefault(num, 0)" -> 해당 값이 없으면 0으로 if문으로 해당 배열의 값이 leaderCount보다 크면 leader와 leaderCount를 해당 값으로 세팅

반복문이 끝나고 leaderCount <= N / 2 일 경우는 리더가 없기에 0을 리턴

A만큼 반복문을 다시 돌려 A[i]가 리더값인 경우를 체크해 이퀴 리더를 카운팅합니다.

제출결과

문제풀어보기 -> https://app.codility.com/programmers/lessons/8-leader/equi_leader/

An array A consisting of N integers is given. The dominator of array A is the value that occurs in more than half of the elements of A.

For example, consider array A such that

A[0] = 3 A[1] = 4 A[2] = 3 A[3] = 2 A[4] = 3 A[5] = -1 A[6] = 3 A[7] = 3 The dominator of A is 3 because it occurs in 5 out of 8 elements of A (namely in those with indices 0, 2, 4, 6 and 7) and 5 is more than a half of 8.

Write a function

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

that, given an array A consisting of N integers, returns index of any element of array A in which the dominator of A occurs. The function should return −1 if array A does not have a dominator.

For example, given array A such that

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

Write an efficient algorithm for the following assumptions:

N is an integer within the range [0..100,000]; each element of array A is an integer within the range [−2,147,483,648..2,147,483,647].

배열 A가 N개의 정수로 구성되어 있습니다. 배열 A의 지배자는 A의 요소의 절반 이상에서 발생하는 값입니다.

예를 들어, 배열 A가 다음과 같다고 가정합니다:

A[0] = 3 A[1] = 4 A[2] = 3 A[3] = 2 A[4] = 3 A[5] = -1 A[6] = 3 A[7] = 3 배열 A의 지배자는 3입니다. 왜냐하면 3은 A의 8개의 요소 중 5개 요소(즉, 인덱스 0, 2, 4, 6, 7에서)에서 발생하며, 5는 8의 절반 이상이기 때문입니다.

다음과 같은 함수를 작성하세요:

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

이 함수는 N개의 정수로 구성된 배열 A가 주어졌을 때, 배열 A의 지배자가 발생하는 요소의 인덱스를 반환합니다. 배열 A에 지배자가 없는 경우 함수는 -1을 반환해야 합니다.

예를 들어, 배열 A가 다음과 같다고 가정합니다:

A[0] = 3 A[1] = 4 A[2] = 3 A[3] = 2 A[4] = 3 A[5] = -1 A[6] = 3 A[7] = 3 함수는 0, 2, 4, 6 또는 7을 반환할 수 있습니다.

다음 가정을 위한 효율적인 알고리즘을 작성하세요:

N은 [0…100,000] 범위 내의 정수입니다. 배열 A의 각 요소는 [−2,147,483,648…2,147,483,647] 범위 내의 정수입니다.

문제풀이

import java.util.*;

class Solution {
    public int solution(int[] A) {
        if (A.length == 0) return -1;

        Map<Integer, Integer> countMap = new HashMap<>();
        int dominator = A[0];
        int maxCount = 0;

        for (int num : A) {
            countMap.put(num, countMap.getOrDefault(num, 0) + 1);
            if (countMap.get(num) > maxCount) {
                maxCount = countMap.get(num);
                dominator = num;
            }
        }

        if (maxCount <= A.length / 2) return -1;

        for (int i = 0; i < A.length; i++) {
            if (A[i] == dominator) return i;
        }

        return -1;
    }
}

해시맵을 사용하여 동일항목을 체크하고 그 수를 저장하여 문제를 풀이

제출결과

문제풀어보기 -> https://app.codility.com/programmers/lessons/8-leader/dominator/

You are going to build a stone wall. The wall should be straight and N meters long, and its thickness should be constant; however, it should have different heights in different places. The height of the wall is specified by an array H of N positive integers. H[I] is the height of the wall from I to I+1 meters to the right of its left end. In particular, H[0] is the height of the wall's left end and H[N−1] is the height of the wall's right end.

The wall should be built of cuboid stone blocks (that is, all sides of such blocks are rectangular). Your task is to compute the minimum number of blocks needed to build the wall.

Write a function:

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

that, given an array H of N positive integers specifying the height of the wall, returns the minimum number of blocks needed to build it.

For example, given array H containing N = 9 integers:

H[0] = 8 H[1] = 8 H[2] = 5 H[3] = 7 H[4] = 9 H[5] = 8 H[6] = 7 H[7] = 4 H[8] = 8 the function should return 7. The figure shows one possible arrangement of seven blocks.

Write an efficient algorithm for the following assumptions:

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

당신은 돌벽을 쌓으려고 합니다. 벽은 직선으로 N 미터 길이여야 하고, 두께는 일정해야 하지만, 높이는 장소마다 다르게 해야 합니다. 벽의 높이는 N개의 양의 정수로 이루어진 배열 H로 지정됩니다. H[I]는 벽의 왼쪽 끝에서 오른쪽으로 I에서 I+1 미터까지의 높이입니다. 특히, H[0]은 벽의 왼쪽 끝의 높이이고, H[N−1]은 벽의 오른쪽 끝의 높이입니다.

벽은 직육면체 돌 블록으로 만들어져야 합니다 (즉, 이러한 블록의 모든 면은 직사각형입니다). 당신의 과제는 벽을 쌓는 데 필요한 최소 블록 수를 계산하는 것입니다.

다음과 같은 함수를 작성하세요:

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

배열 H가 N개의 양의 정수를 포함하고 있을 때, 벽의 높이를 지정하는 배열 H가 주어지면, 벽을 쌓는 데 필요한 최소 블록 수를 반환하는 함수를 작성하세요.

예를 들어, N = 9인 배열 H가 주어졌을 때:

H[0] = 8    H[1] = 8    H[2] = 5
H[3] = 7    H[4] = 9    H[5] = 8
H[6] = 7    H[7] = 4    H[8] = 8

함수는 7을 반환해야 합니다. 그림은 7개의 블록으로 가능한 배치를 보여줍니다.

다음 가정을 위한 효율적인 알고리즘을 작성하세요:

N은 [1…100,000] 범위 내의 정수입니다. 배열 H의 각 요소는 [1…1,000,000,000] 범위 내의 정수입니다.

문제풀이

import java.util.Stack;

class Solution {
    public int solution(int[] H) {
        Stack<Integer> stack = new Stack<>();
        int blockCount = 0;

        for (int height : H) {
            while (!stack.isEmpty() && stack.peek() > height) {
                stack.pop();
            }
            if (stack.isEmpty() || stack.peek() < height) {
                stack.push(height);
                blockCount++;
            }
        }

        return blockCount;
    }
}

위 문제는 계속 제출 시에 계속 오답처리가되어 해설을 참고했습니다 ㅠㅠ

문제의 지문이 이해가 잘 안되는 부분들이 있는데 해당 문제는 블록이 바로 이전 블록과 동일하면 블록 변경이 없고 높이가 변하면 블록을 다른 블록으로 변경하고 블록 수를 추가하면 됩니다.

예를 들어, 주어진 배열 H = [8, 8, 5, 7, 9, 8, 7, 4, 8]의 경우

처음에 높이 8로 시작합니다. 첫 번째 블록을 추가합니다. 두 번째 위치에서도 높이 8이므로 같은 블록을 유지합니다. 세 번째 위치에서 높이가 5로 감소합니다. 새로운 블록을 추가합니다. 네 번째 위치에서 높이가 7로 증가합니다. 새로운 블록을 추가합니다. 다섯 번째 위치에서 높이가 9로 증가합니다. 새로운 블록을 추가합니다. 여섯 번째 위치에서 높이가 8로 감소합니다. 새로운 블록을 추가합니다. 일곱 번째 위치에서 높이가 7로 감소합니다. 새로운 블록을 추가합니다. 여덟 번째 위치에서 높이가 4로 감소합니다. 새로운 블록을 추가합니다. 아홉 번째 위치에서 높이가 8로 증가합니다. 새로운 블록을 추가합니다. 이렇게 하면 총 7개의 블록이 필요합니다.

여기서 첫번째 블록은 항상 필요하므로 별도로 세지않고 기본 블록으로 간주하여 새로 추가되는 블록의 갯수만을 카운팅해야 합니다.

제출결과

문제풀어보기 -> https://app.codility.com/programmers/lessons/7-stacks_and_queues/stone_wall/

A string S consisting of N characters is called properly nested if:

S is empty; S has the form "(U)" where U is a properly nested string; S has the form "VW" where V and W are properly nested strings. For example, string "(()(())())" is properly nested but string "())" isn't.

Write a function:

class Solution { public int solution(String S); }

that, given a string S consisting of N characters, returns 1 if string S is properly nested and 0 otherwise.

For example, given S = "(()(())())", the function should return 1 and given S = "())", the function should return 0, as explained above.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [0..1,000,000]; string S is made only of the characters '(' and/or ')'.

문자열 S가 N개의 문자로 구성되어 있을 때, 다음 조건을 만족하면 S는 올바르게 중첩된 문자열이라고 합니다:

S가 비어있다. S가 “(U)” 형태를 가지며, 여기서 U는 올바르게 중첩된 문자열이다. S가 “VW” 형태를 가지며, 여기서 V와 W는 올바르게 중첩된 문자열이다. 예를 들어, 문자열 "(()(())())"는 올바르게 중첩된 문자열이지만, 문자열 "())"는 그렇지 않습니다.

다음과 같은 함수를 작성하세요:

class Solution { 
    public int solution(String S); 
}

이 함수는 N개의 문자로 구성된 문자열 S가 주어졌을 때, 문자열 S가 올바르게 중첩된 경우 1을 반환하고, 그렇지 않은 경우 0을 반환해야 합니다.

예를 들어, S = "(()(())())"가 주어지면 함수는 1을 반환해야 하고, S = "())"가 주어지면 함수는 0을 반환해야 합니다.

다음 가정을 만족하는 효율적인 알고리즘을 작성하세요:

N은 [0…1,000,000] 범위 내의 정수입니다. 문자열 S는 오직 '('와 ‘)’ 문자로만 구성됩니다.

문제풀이

ort java.util.*;

class Solution {
    public int solution(String S) {
        int length = S.length();
        int setCount = 0;
        String[] array = S.split("");
        Stack<String> stack = new Stack<>();

        if(length == 0){
            return 1;
        }
        for(int i = 0; i < length; i++){
            if(array[i].equals("(")){
                stack.push(array[i]);
                setCount++;
            }else{
                if(setCount != 0){
                    stack.pop();    
                    setCount--;
                }else{
                    return 0;
                }
            }
        }
        if(setCount == 0){
            return 1;
        }
        return 0;
    }
}

arraylist(문자열 잘라서 저장)과 stack을 사용하여 짝이 맞는 경우에는 1을 리턴 짝이 맞지 않는 경우에는 0을 리턴해줌

제출결과 75%의 정답률 타임 아웃에러 발생으로 코드를 수정하였음

수정코드

import java.util.*;

class Solution {
    public int solution(String S) {
        int length = S.length();
        Stack<Character> stack = new Stack<>();

        if (length == 0) {
            return 1;
        }
        for (int i = 0; i < length; i++) {
            char currentChar = S.charAt(i);
            if (currentChar == '(') {
                stack.push(currentChar);
            } else {
                if (!stack.isEmpty()) {
                    stack.pop();
                } else {
                    return 0;
                }
            }
        }
        return stack.isEmpty() ? 1 : 0;
    }
}

배열에 String을 분리하여 저장하지 않고 char currentChar = S.charAt(i);를 사용, Stack은 String타입이 아닌 Character 타입으로 변경 setCount변수를 사용하지 않고 stack의 크기만 확인하였습니다.

제출결과

문제풀어보기 -> https://app.codility.com/programmers/lessons/7-stacks_and_queues/nesting/

You are given two non-empty arrays A and B consisting of N integers. Arrays A and B represent N voracious fish in a river, ordered downstream along the flow of the river.

The fish are numbered from 0 to N − 1. If P and Q are two fish and P < Q, then fish P is initially upstream of fish Q. Initially, each fish has a unique position.

Fish number P is represented by A[P] and B[P]. Array A contains the sizes of the fish. All its elements are unique. Array B contains the directions of the fish. It contains only 0s and/or 1s, where:

0 represents a fish flowing upstream, 1 represents a fish flowing downstream. If two fish move in opposite directions and there are no other (living) fish between them, they will eventually meet each other. Then only one fish can stay alive − the larger fish eats the smaller one. More precisely, we say that two fish P and Q meet each other when P < Q, B[P] = 1 and B[Q] = 0, and there are no living fish between them. After they meet:

If A[P] > A[Q] then P eats Q, and P will still be flowing downstream, If A[Q] > A[P] then Q eats P, and Q will still be flowing upstream. We assume that all the fish are flowing at the same speed. That is, fish moving in the same direction never meet. The goal is to calculate the number of fish that will stay alive.

For example, consider arrays A and B such that:

A[0] = 4 B[0] = 0 A[1] = 3 B[1] = 1 A[2] = 2 B[2] = 0 A[3] = 1 B[3] = 0 A[4] = 5 B[4] = 0 Initially all the fish are alive and all except fish number 1 are moving upstream. Fish number 1 meets fish number 2 and eats it, then it meets fish number 3 and eats it too. Finally, it meets fish number 4 and is eaten by it. The remaining two fish, number 0 and 4, never meet and therefore stay alive.

Write a function:

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

that, given two non-empty arrays A and B consisting of N integers, returns the number of fish that will stay alive.

For example, given the arrays shown above, the function should return 2, as explained above.

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 [0..1,000,000,000]; each element of array B is an integer that can have one of the following values: 0, 1; the elements of A are all distinct.

두 개의 비어 있지 않은 배열 A와 B가 N개의 정수로 구성되어 있습니다. 배열 A와 B는 강에서 N마리의 탐욕스러운 물고기를 나타내며, 강의 흐름을 따라 하류로 정렬되어 있습니다.

물고기는 0부터 N-1까지 번호가 매겨져 있습니다. 만약 P와 Q가 두 마리의 물고기이고 P < Q라면, 물고기 P는 처음에 물고기 Q의 상류에 있습니다. 처음에는 각 물고기가 고유한 위치를 가지고 있습니다.

물고기 번호 P는 A[P]와 B[P]로 나타냅니다. 배열 A는 물고기의 크기를 포함하고 있습니다. 모든 요소는 고유합니다. 배열 B는 물고기의 방향을 포함하고 있습니다. 0과 1만 포함하고 있으며:

0은 상류로 흐르는 물고기를 나타냅니다. 1은 하류로 흐르는 물고기를 나타냅니다. 두 물고기가 반대 방향으로 움직이고 그들 사이에 다른 (살아있는) 물고기가 없다면, 결국 서로 만나게 됩니다. 그러면 한 마리의 물고기만 살아남을 수 있습니다. 더 큰 물고기가 더 작은 물고기를 먹습니다. 더 정확히 말하면, 두 물고기 P와 Q가 서로 만난다고 할 때, P < Q, B[P] = 1, B[Q] = 0이고 그들 사이에 살아있는 물고기가 없을 때입니다. 그들이 만난 후:

만약 A[P] > A[Q]라면 P가 Q를 먹고, P는 여전히 하류로 흐릅니다. 만약 A[Q] > A[P]라면 Q가 P를 먹고, Q는 여전히 상류로 흐릅니다. 모든 물고기는 동일한 속도로 흐른다고 가정합니다. 즉, 같은 방향으로 움직이는 물고기는 절대 만나지 않습니다. 목표는 살아남을 물고기의 수를 계산하는 것입니다.

예를 들어, 다음과 같은 배열 A와 B를 고려해보세요:

A[0] = 4    B[0] = 0
A[1] = 3    B[1] = 1
A[2] = 2    B[2] = 0
A[3] = 1    B[3] = 0
A[4] = 5    B[4] = 0

처음에는 모든 물고기가 살아있고, 물고기 번호 1을 제외한 모든 물고기가 상류로 이동합니다. 물고기 번호 1은 물고기 번호 2를 만나서 먹고, 그 다음 물고기 번호 3을 만나서 먹습니다. 마지막으로 물고기 번호 4를 만나서 먹힙니다. 남은 두 마리의 물고기, 번호 0과 4는 서로 만나지 않으므로 살아남습니다.

다음과 같은 함수를 작성하세요:

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

두 개의 비어 있지 않은 배열 A와 B가 N개의 정수로 구성되어 있을 때, 살아남을 물고기의 수를 반환합니다.

예를 들어, 위에서 보여준 배열이 주어지면 함수는 2를 반환해야 합니다.

다음 가정을 위한 효율적인 알고리즘을 작성하세요:

N은 [1…100,000] 범위 내의 정수입니다. 배열 A의 각 요소는 [0…1,000,000,000] 범위 내의 정수입니다. 배열 B의 각 요소는 0 또는 1 값을 가질 수 있습니다. 배열 A의 요소는 모두 고유합니다.

문제풀이

import java.util.*;

class Solution {
    public int solution(int[] A, int[] B) {
        int fishs = 0;
        Stack<Integer> downfish = new Stack<>();
        for (int i = 0; i < A.length; i++) {
            if (B[i] == 1) { // 1일 경우(하류)
                downfish.push(A[i]);
            } else { // 0일 경우(상류)
                while (!downfish.isEmpty()) {
                    if (downfish.peek() > A[i]) {
                        break;
                    } else {
                        downfish.pop();
                    }
                }
                if (downfish.isEmpty()) {
                    fishs++;
                }
            }
        }
        fishs += downfish.size();

        return fishs;
    }
}

하류로 흐르는 물고기(B[i] == 1)는 스택에 추가 상류로 흐르는 물고기(B[i] == 0)를 만날 때, 스택에서 하류로 흐르는 물고기를 꺼내어 크기를 비교하여 더 큰 물고기가 살아남고, 작은 물고기는 제거합니다.

모든 물고기를 처리한 후, 스택에 남아 있는 하류로 흐르는 물고기와 상류로 흐르는 물고기의 수를 합하여 최종 결과를 반환

제출결과

문제풀어보기 -> https://app.codility.com/programmers/lessons/7-stacks_and_queues/fish/

A string S consisting of N characters is considered to be properly nested if any of the following conditions is true:

S is empty; S has the form "(U)" or "[U]" or "{U}" where U is a properly nested string; S has the form "VW" where V and W are properly nested strings. For example, the string "{[()()]}" is properly nested but "([)()]" is not.

Write a function:

class Solution { public int solution(String S); }

that, given a string S consisting of N characters, returns 1 if S is properly nested and 0 otherwise.

For example, given S = "{[()()]}", the function should return 1 and given S = "([)()]", the function should return 0, as explained above.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [0..200,000]; string S is made only of the following characters: '(', '{', '[', ']', '}' and/or ')'.

문자열 S가 다음 조건 중 하나를 만족하면 올바르게 중첩된 것으로 간주됩니다:

S가 비어 있습니다. S가 “(U)” 또는 “[U]” 또는 “{U}” 형태를 가지며, 여기서 U는 올바르게 중첩된 문자열입니다. S가 “VW” 형태를 가지며, 여기서 V와 W는 올바르게 중첩된 문자열입니다. 예를 들어, 문자열 "{[()()]}"는 올바르게 중첩된 것이지만 "([)()]"는 그렇지 않습니다.

N개의 문자로 구성된 문자열 S가 주어졌을 때, S가 올바르게 중첩된 경우 1을 반환하고 그렇지 않은 경우 0을 반환합니다.

예를 들어, S = "{[()()]}"가 주어지면 함수는 1을 반환해야 하고, S = "([)()]"가 주어지면 함수는 0을 반환해야 합니다.

다음 가정을 위한 효율적인 알고리즘을 작성하세요:

N은 [0…200,000] 범위 내의 정수입니다. 문자열 S는 ‘(’, ‘{’, ‘[’, ‘]’, ‘}’ 및/또는 ‘)’ 문자로만 구성됩니다.

즉 괄호가 전부 올바르게 닫히는 경우에는 1을 반환 괄호가 올바르게 닫히지 않는 경우에는 0을 반환하면 됩니다.

문제풀이

import java.util.*;

class Solution {
    public int solution(String S) {
        Stack<Character> stack = new Stack<>();
        for (char ch : S.toCharArray()) {
            if (ch == '{' || ch == '[' || ch == '(') {
                stack.push(ch);
            } else {
                if (stack.isEmpty()) {
                    return 0;
                }
                char last = stack.pop();
                if ((ch == '}' && last != '{') || 
                    (ch == ']' && last != '[') || 
                    (ch == ')' && last != '(')) {
                    return 0;
                }
            }
        }
        return stack.isEmpty() ? 1 : 0;
    }
}

스택을 사용하여 짝이 맞는지 확인 " {, [, ( "일 경우에는 스택에 푸시 " }, ], ) "일 경우에는 짝이 맞는지 확인 후 짝이 맞지 않으면 0을 반환

제출결과

문제풀어보기 -> https://app.codility.com/programmers/lessons/7-stacks_and_queues/brackets/

We draw N discs on a plane. The discs are numbered from 0 to N − 1. An array A of N non-negative integers, specifying the radiuses of the discs, is given. The J-th disc is drawn with its center at (J, 0) and radius A[J].

We say that the J-th disc and K-th disc intersect if J ≠ K and the J-th and K-th discs have at least one common point (assuming that the discs contain their borders).

The figure below shows discs drawn for N = 6 and A as follows:

A[0] = 1 A[1] = 5 A[2] = 2 A[3] = 1 A[4] = 4 A[5] = 0

There are eleven (unordered) pairs of discs that intersect, namely:

discs 1 and 4 intersect, and both intersect with all the other discs; disc 2 also intersects with discs 0 and 3. Write a function:

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

that, given an array A describing N discs as explained above, returns the number of (unordered) pairs of intersecting discs. The function should return −1 if the number of intersecting pairs exceeds 10,000,000.

Given array A shown above, the function should return 11, as explained above.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [0..100,000]; each element of array A is an integer within the range [0..2,147,483,647].

우리는 평면에 N개의 원을 그립니다. 원은 0부터 N-1까지 번호가 매겨져 있습니다. N개의 비음수 정수로 구성된 배열 A가 주어지며, 이는 원의 반지름을 나타냅니다. J번째 원은 중심이 (J, 0)이고 반지름이 A[J]입니다.

J번째 원과 K번째 원이 서로 다른 경우(J ≠ K) 두 원이 적어도 하나의 공통점을 가지면 두 원이 교차한다고 합니다(원의 경계가 포함된다고 가정합니다).

다음 그림은 N = 6이고 배열 A가 다음과 같은 경우 그려진 원을 보여줍니다:

A[0] = 1 A[1] = 5 A[2] = 2 A[3] = 1 A[4] = 4 A[5] = 0

교차하는 원의 쌍은 총 11개입니다:

원 1과 원 4가 교차하며, 둘 다 다른 모든 원과 교차합니다. 원 2도 원 0과 원 3과 교차합니다.

위에서 설명한 대로 배열 A가 주어졌을 때 교차하는 원의 (순서 없는) 쌍의 수를 반환합니다. 교차하는 쌍의 수가 10,000,000을 초과하면 함수는 -1을 반환해야 합니다.

위에서 주어진 배열 A의 경우 함수는 11을 반환해야 합니다.

다음 가정을 만족하는 효율적인 알고리즘을 작성하세요:

N은 [0…100,000] 범위 내의 정수입니다. 배열 A의 각 요소는 [0…2,147,483,647] 범위 내의 정수입니다.

문제풀이

import java.util.*;

class Solution {
    public int solution(int[] A) {
        int N = A.length;
        if (N < 2) return 0;

        // 시작 지점과 끝 지점을 저장할 배열
        long[] start = new long[N];
        long[] end = new long[N];

        for (int i = 0; i < N; i++) {
            start[i] = (long)i - A[i];
            end[i] = (long)i + A[i];
        }

        // 시작 지점과 끝 지점을 정렬
        Arrays.sort(start);
        Arrays.sort(end);

        int intersections = 0;
        int activeDiscs = 0;
        int j = 0;

        for (int i = 0; i < N; i++) {
            while (j < N && end[j] < start[i]) {
                activeDiscs--;
                j++;
            }
            intersections += activeDiscs;
            if (intersections > 10000000) return -1;
            activeDiscs++;
        }

        return intersections;
    }
}

N이 2보다 작으면 교차하는 원이 없으므로 0을 반환합니다.

원의 시작 지점은 (long)i - A[i] start에, 끝 지점은 (long)i + A[i] end에 배열로 저장 후

start와 end 배열을 각각 오름차순으로 정렬

intersections 변수 : 교차하는 원의 쌍의 수 activeDiscs 변수 : 현재 교차하는 원의 수

start 배열을 순회하면서 각 원의 시작 지점을 확인 while 루프를 사용하여 현재 원의 시작 지점보다 작은 끝 지점을 가진 원의 수를 감소

intersections에 현재 교차하는 원의 수를 더합니다.

교차하는 원의 쌍의 수가 10,000,000을 초과하면 -1을 반환합니다. 현재 원을 교차하는 원으로 추가

제출결과

문제풀어보기 -> https://app.codility.com/programmers/lessons/6-sorting/number_of_disc_intersections/

A[P] + A[Q] > A[R], A[Q] + A[R] > A[P], A[R] + A[P] > A[Q]. For example, consider array A such that:

A[0] = 10 A[1] = 2 A[2] = 5 A[3] = 1 A[4] = 8 A[5] = 20 Triplet (0, 2, 4) is triangular.

Write a function:

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

that, given an array A consisting of N integers, returns 1 if there exists a triangular triplet for this array and returns 0 otherwise.

For example, given array A such that:

A[0] = 10 A[1] = 2 A[2] = 5 A[3] = 1 A[4] = 8 A[5] = 20 the function should return 1, as explained above. Given array A such that:

A[0] = 10 A[1] = 50 A[2] = 5 A[3] = 1 the function should return 0.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [0..100,000]; each element of array A is an integer within the range [−2,147,483,648..2,147,483,647].

배열 A가 N개의 정수로 구성되어 있습니다. 삼중항 (P, Q, R)은 다음 조건을 만족할 때 삼각형입니다:

0 ≤ P < Q < R < N 이고,

A[P] + A[Q] > A[R], A[Q] + A[R] > A[P], A[R] + A[P] > A[Q].

예를 들어, 배열 A가 다음과 같다고 가정합니다:

A[0] = 10 A[1] = 2 A[2] = 5 A[3] = 1 A[4] = 8 A[5] = 20

삼중항 (0, 2, 4)는 삼각형입니다.

N개의 정수로 구성된 배열 A가 주어졌을 때, 삼각형 삼중항이 존재하면 1을 반환하고, 그렇지 않으면 0을 반환합니다.

예를 들어, 배열 A가 다음과 같다고 가정합니다:

A[0] = 10 A[1] = 2 A[2] = 5 A[3] = 1 A[4] = 8 A[5] = 20

이 함수는 위에서 설명한 대로 1을 반환해야 합니다. 배열 A가 다음과 같다고 가정합니다:

A[0] = 10 A[1] = 50 A[2] = 5 A[3] = 1

이 함수는 0을 반환해야 합니다.

다음 가정을 만족하는 효율적인 알고리즘을 작성하세요:

N은 [0…100,000] 범위 내의 정수입니다. 배열 A의 각 요소는 [−2,147,483,648…2,147,483,647] 범위 내의 정수입니다.

문제풀이

import java.util.*;

class Solution {
    public int solution(int[] A) {
        // 3이하인 경우 삼각형 존재 불가
        if (A.length < 3) {
            return 0;
        }

        // 배열을 오름차순으로 정렬
        Arrays.sort(A);

        for (int i = 0; i < A.length - 2; i++) {
            long P = A[i];
            long Q = A[i+1];
            long R = A[i+2];
            if (P > 0 && P + Q > R) {
                return 1;
            }
        }
        return 0;
    }
}

특이사항으로 계산시 int 범위를 넘어가는 경우가 있어 long 타입으로 변환해서 문제풀이를 하였습니다.

제출결과

문제풀어보기 -> https://app.codility.com/programmers/lessons/6-sorting/triangle/

A non-empty array A consisting of N integers is given. The product of triplet (P, Q, R) equates to A[P] * A[Q] * A[R] (0 ≤ P < Q < R < N).

For example, array A such that:

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

(0, 1, 2), product is −3 * 1 * 2 = −6 (1, 2, 4), product is 1 * 2 * 5 = 10 (2, 4, 5), product is 2 * 5 * 6 = 60 Your goal is to find the maximal product of any triplet.

Write a function:

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

that, given a non-empty array A, returns the value of the maximal product of any triplet.

For example, given array A such that:

A[0] = -3 A[1] = 1 A[2] = 2 A[3] = -2 A[4] = 5 A[5] = 6 the function should return 60, as the product of triplet (2, 4, 5) is maximal.

Write an efficient algorithm for the following assumptions:

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

주어진 N개의 정수로 구성된 비어 있지 않은 배열 A가 있습니다. 삼중항 (P, Q, R)의 곱은 A[P] * A[Q] * A[R] (0 ≤ P < Q < R < N)입니다.

예를 들어, 배열 A가 다음과 같을 때:

A[0] = -3 A[1] = 1 A[2] = 2 A[3] = -2 A[4] = 5 A[5] = 6 다음과 같은 예시 삼중항이 포함됩니다:

(0, 1, 2), 곱은 −3 * 1 * 2 = −6 (1, 2, 4), 곱은 1 * 2 * 5 = 10 (2, 4, 5), 곱은 2 * 5 * 6 = 60 당신의 목표는 어떤 삼중항의 최대 곱을 찾는 것입니다.

비어 있지 않은 배열 A가 주어졌을 때, 어떤 삼중항의 최대 곱의 값을 반환하는 함수를 작성하세요.

예를 들어, 배열 A가 다음과 같을 때:

A[0] = -3 A[1] = 1 A[2] = 2 A[3] = -2 A[4] = 5 A[5] = 6 함수는 삼중항 (2, 4, 5)의 곱이 최대이므로 60을 반환해야 합니다.

N은 [3…100,000] 범위 내의 정수입니다; 배열 A의 각 요소는 [−1,000…1,000] 범위 내의 정수입니다.

문제풀이

import java.util.Arrays;

class Solution {
    public int solution(int[] A) {
        Arrays.sort(A);
        int n = A.length;
        int maxProduct = Math.max(A[0] * A[1] * A[n-1], A[n-1] * A[n-2] * A[n-3]);
        return maxProduct;
    }
}

배열을 정렬한 후, 가장 작은 두 값과 가장 큰 값을 곱한 값과 가장 큰 세 값을 곱한 값 중 최대값을 반환합니다.

제출결과

문제풀어보기 -> https://app.codility.com/programmers/lessons/6-sorting/max_product_of_three/

Write a function

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

that, given an array A consisting of N integers, returns the number of distinct values in array A.

For example, given array A consisting of six elements such that:

A[0] = 2 A[1] = 1 A[2] = 1 A[3] = 2 A[4] = 3 A[5] = 1 the function should return 3, because there are 3 distinct values appearing in array A, namely 1, 2 and 3.

Write an efficient algorithm for the following assumptions:

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

다음과 같은 함수

Java

class Solution { public int solution(int[] A); } AI가 생성한 코드입니다. 신중하게 검토하고 사용하세요. FAQ의 자세한 정보. 가 주어졌을 때, N개의 정수로 구성된 배열 A가 주어지면, 배열 A에서 서로 다른 값의 개수를 반환하는 함수를 작성하세요.

예를 들어, 다음과 같이 6개의 요소로 구성된 배열 A가 주어졌을 때:

A[0] = 2 A[1] = 1 A[2] = 1 A[3] = 2 A[4] = 3 A[5] = 1

함수는 배열 A에 나타나는 서로 다른 값이 3개이므로 3을 반환해야 합니다. 즉, 1, 2, 3이라는 서로 다른 값이 배열 A에 나타납니다.

다음 가정을 위한 효율적인 알고리즘을 작성하세요:

N은 [0…100,000] 범위 내의 정수입니다. 배열 A의 각 요소는 [−1,000,000…1,000,000] 범위 내의 정수입니다.

문제풀이

import java.util.*;

class Solution {
    public int solution(int[] A) {
        HashSet<Integer> set = new HashSet<>();
        for(int i = 0; i < A.length; i++){
            set.add(A[i]);
        }
        return set.size();
    }
}

제출결과 해쉬셋을 통해 같은 값은 1번만 저장하고 해당 해쉬셋의 사이즈를 리턴

문제풀어보기 -> https://app.codility.com/programmers/lessons/6-sorting/distinct/

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].

비어 있지 않은 N개의 정수로 구성된 배열 A가 주어집니다. 0 ≤ P < Q < N인 두 정수 (P, Q) 쌍은 배열 A의 슬라이스라고 합니다 (슬라이스는 최소 두 개의 요소를 포함합니다). 슬라이스 (P, Q)의 평균은 A[P] + A[P + 1] + … + A[Q]의 합을 슬라이스의 길이로 나눈 값입니다. 정확히 말하면, 평균은 (A[P] + A[P + 1] + … + A[Q]) / (Q − P + 1)입니다.

예를 들어, 배열 A가 다음과 같다면:

A[0] = 4 A[1] = 2 A[2] = 2 A[3] = 5 A[4] = 1 A[5] = 5 A[6] = 8

다음과 같은 예제 슬라이스가 포함됩니다:

슬라이스 (1, 2), 평균은 (2 + 2) / 2 = 2; 슬라이스 (3, 4), 평균은 (5 + 1) / 2 = 3; 슬라이스 (1, 4), 평균은 (2 + 2 + 5 + 1) / 4 = 2.5. 목표는 평균이 최소인 슬라이스의 시작 위치를 찾는 것입니다.

비어 있지 않은 N개의 정수로 구성된 배열 A가 주어지면, 평균이 최소인 슬라이스의 시작 위치를 반환합니다. 평균이 최소인 슬라이스가 여러 개 있는 경우, 그러한 슬라이스의 가장 작은 시작 위치를 반환해야 합니다.

예를 들어, 배열 A가 다음과 같다면:

A[0] = 4 A[1] = 2 A[2] = 2 A[3] = 5 A[4] = 1 A[5] = 5 A[6] = 8

함수는 1을 반환해야 합니다.

다음 가정을 위한 효율적인 알고리즘을 작성하세요:

N은 [2…100,000] 범위 내의 정수입니다. 배열 A의 각 요소는 [−10,000…10,000] 범위 내의 정수입니다.

문제풀이

import java.util.*;

class Solution {
    public int solution(int[] A) {
        int N = A.length;
        int minIndex = 0;
        double minAvg = (A[0] + A[1]) / 2.0;

        for (int i = 0; i < N - 2; i++) {
            double avg2 = (A[i] + A[i + 1]) / 2.0;
            double avg3 = (A[i] + A[i + 1] + A[i + 2]) / 3.0;

            if (avg2 < minAvg) {
                minAvg = avg2;
                minIndex = i;
            }
            if (avg3 < minAvg) {
                minAvg = avg3;
                minIndex = i;
            }
        }

        double lastAvg = (A[N - 2] + A[N - 1]) / 2.0;
        if (lastAvg < minAvg) {
            minAvg = lastAvg;
            minIndex = N - 2;
        }

        return minIndex;
    }
}

예제로 주어진 슬라이스의 평균을 계산해보면 보통 2,3선에서 끊기는 평균이 그 이상보다 작은 것을 볼 수 있습니다. 길이가 2,3인 모든 평균을 계산하면서 최소 평균을 찾습니다. 추가적으로 평균을 찾을때 최소 평균을 찾은 슬라이스의 시작인덱스를 업데이트해줍니다.

처음 제출시에 틀렸던 부분으로 주의 할 점은 for문을 사용시에 배열A의 크기만큼 for문을 돌리면 평균값을 구할 때 -> double avg2 = (A[i] + A[i + 1]) / 2.0; double avg3 = (A[i] + A[i + 1] + A[i + 2]) / 3.0; i + 1, i + 2 때문에 배열 범위에서 나가버리는 문제가 발생하기 때문에 반복문에서는 반복범위를 N - 2까지 잡아주고 반복문이 끝난 후 마지막 슬라이스 요소를 따로 계산해줍니다.

제출결과

문제풀어보기 -> https://app.codility.com/programmers/lessons/5-prefix_sums/min_avg_two_slice/

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 and 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.

DNA 서열은 A, C, G, T 문자로 구성된 문자열로 표현될 수 있습니다. 각 문자는 연속적인 뉴클레오타이드의 종류를 나타냅니다. 각 뉴클레오타이드는 영향 인자(impact factor)를 가지며, 이는 정수입니다. A, C, G, T 유형의 뉴클레오타이드는 각각 1, 2, 3, 4의 영향 인자를 가집니다. 여러분은 주어진 DNA 서열의 특정 부분에 포함된 뉴클레오타이드의 최소 영향 인자를 묻는 여러 쿼리에 답해야 합니다.

DNA 서열은 N개의 문자로 구성된 비어 있지 않은 문자열 S = S[0]S[1]…S[N-1]로 주어집니다. M개의 쿼리가 있으며, 각 쿼리는 M개의 정수로 구성된 비어 있지 않은 배열 P와 Q로 주어집니다. K번째 쿼리(0 ≤ K < M)는 P[K]와 Q[K] 사이(포함)의 DNA 서열에 포함된 뉴클레오타이드의 최소 영향 인자를 찾아야 합니다.

예를 들어, 문자열 S = CAGCCTA와 배열 P, Q가 다음과 같다고 가정합니다

P[0] = 2 Q[0] = 4 P[1] = 5 Q[1] = 5 P[2] = 0 Q[2] = 6

이 M = 3개의 쿼리에 대한 답은 다음과 같습니다:

위치 2에서 4 사이의 DNA 부분에는 뉴클레오타이드 G와 C(두 번)가 포함되어 있으며, 이들의 영향 인자는 각각 3과 2이므로 답은 2입니다. 위치 5에서 5 사이의 부분에는 단일 뉴클레오타이드 T가 포함되어 있으며, 이의 영향 인자는 4이므로 답은 4입니다. 위치 0에서 6 사이의 전체 문자열에는 모든 뉴클레오타이드가 포함되어 있으며, 특히 영향 인자가 1인 뉴클레오타이드 A가 포함되어 있으므로 답은 1입니다.

예를 들어, 문자열 S = CAGCCTA와 배열 P, Q가 다음과 같다면:

P[0] = 2 Q[0] = 4 P[1] = 5 Q[1] = 5 P[2] = 0 Q[2] = 6

함수는 [2, 4, 1] 값을 반환해야 합니다.

다음 가정을 위한 효율적인 알고리즘을 작성하세요:

N은 [1…100,000] 범위 내의 정수입니다. M은 [1…50,000] 범위 내의 정수입니다. 배열 P와 Q의 각 요소는 [0…N - 1] 범위 내의 정수입니다. P[K] ≤ Q[K], 여기서 0 ≤ K < M입니다. 문자열 S는 대문자 영어 문자 A, C, G, T로만 구성됩니다.

문제풀이

import java.util.*;

class Solution {
    public int[] solution(String S, int[] P, int[] Q) {
        int M = P.length;
        String str = "";
        ArrayList<Integer> result = new ArrayList<>();
        for(int i = 0; i < M; i++){
            str = S.substring(P[i], Q[i] + 1);
            if(str.contains("A")){
                result.add(1);
            }
            else if(str.contains("C")){
                result.add(2);
            }
            else if(str.contains("G")){
                result.add(3);
            }
            else if(str.contains("T")){
                result.add(4);
            }
        }

        int[] resultArray = new int[result.size()];
        for(int i = 0; i < result.size(); i++) {
            resultArray[i] = result.get(i);
        }

        return resultArray;
    }
}

반복문에서 문자열 S를 자른 문자열에 A,C,G,T가 포함되어있는지 확인하고 해당 값에 맞는 정수를 배열에 넣어 값을 리턴해줬습니다.

제출결과

타임아웃 에러발생 해시맵으로 변경해도 동일하게 75%.. 검색해보니 누적 개수를 저장하는 방식으로 문제를 풀 수 있다는 내용을 알았다.

수정된 코드

import java.util.*;

class Solution {
    public int[] solution(String S, int[] P, int[] Q) {
        int N = S.length();
        int M = P.length;
        int[] result = new int[M];

        // 누적 개수 배열 생성
        int[][] prefixSums = new int[4][N + 1];

        for (int i = 0; i < N; i++) {
            char nucleotide = S.charAt(i);
            for (int j = 0; j < 4; j++) {
                prefixSums[j][i + 1] = prefixSums[j][i];
            }
            if (nucleotide == 'A') {
                prefixSums[0][i + 1]++;
            } else if (nucleotide == 'C') {
                prefixSums[1][i + 1]++;
            } else if (nucleotide == 'G') {
                prefixSums[2][i + 1]++;
            } else if (nucleotide == 'T') {
                prefixSums[3][i + 1]++;
            }
        }

        // 각 쿼리에 대해 최소 영향 인자 찾기
        for (int i = 0; i < M; i++) {
            int start = P[i];
            int end = Q[i] + 1;
            if (prefixSums[0][end] - prefixSums[0][start] > 0) {
                result[i] = 1;
            } else if (prefixSums[1][end] - prefixSums[1][start] > 0) {
                result[i] = 2;
            } else if (prefixSums[2][end] - prefixSums[2][start] > 0) {
                result[i] = 3;
            } else if (prefixSums[3][end] - prefixSums[3][start] > 0) {
                result[i] = 4;
            }
        }

        return result;
    }
}

각 쿼리에 대해 부분 문자열을 생성하고 검사하는 대신, 누적 합(prefix sum)을 사용하여 각 쿼리에 대해 빠르게 최소 영향 인자를 찾을 수 있다

제출결과

문제풀어보기-> https://app.codility.com/programmers/lessons/5-prefix_sums/genomic_range_query/