Codility Lesson 04 - MaxCounters( JAVA )

https://app.codility.com/programmers/lessons/4-counting_elements/max_counters/

MaxCounters coding task - Learn to Code - Codility

 

문제

- N counters는 초기에 모두 0으로 초기화되어 있는 구조이다.

- 2가지의 연산방법이 있다.

  - increase(X) : 해당하는 X 순번의 counters의 수를 +1한다.

  - max counter - 모든 counters를 최대값으로 수정한다.

- A는 비어있지 않은 배열로 M개의 정수들로 이루어져 있고, 연속적인 연산들을 표현한다.

  - A[K] = X, 1 <= X <= N일 때, K 연산은 increase(X)를 한다.

  - A[K] = N+1일 때, K는 max counter

- 예시

N = 5,

A[0] = 3, A[1] =4, A[2] = 4, A[3] = 6, A[4] = 1, A[5] = 4, A[6] = 4 일 경우

연산의 결과는

(0, 0, 1, 0, 0)
(0, 0, 1, 1, 0)
(0, 0, 1, 2, 0)
(2, 2, 2, 2, 2)
(3, 2, 2, 2, 2)
(3, 2, 2, 3, 2)
(3, 2, 2, 4, 2)

 

제한조건

• N and M are integers within the range [1..100,000];
• each element of array A is an integer within the range [1..N + 1].

N, M은 1 ~ 100,000 사이의 정수들이다.

A의 각 원소들은 1 ~ N+1 사이의 정수이다.

 

풀이

- for문을 중첩하면 시간복잡도를 넘을 수가 있는 문제이다.( A for문을 돌면서, max counters가 나올 때마다 N counters를 max값으로 다 순회할 경우를 의미 )

- int max = 0, int lower_limit = 0으로 초기화

  - max는 연산 실행 시 최대값을  lower_limit는 max counter 연산시 당시의 max값을 의미한다.

  - max counter 연산 실행 후 increase 연산 시에는 기존 배열의 index 값을 lower_limit와 비교하여 연산한다.

- 모든 for문 순회 후 lower_limit보다 작은 수들은 lower_limit값으로 치환한다.

 

사용한 테스트 케이스

(5, [3, 4, 4, 6, 1, 6, 4])

(5, [3, 4, 4, 6, 1, 6, 4, 5, 1])

(5, [3, 4, 4, 6, 1, 6, 4, 5, 1, 6])

(1, [2])

(1, [1])

 

 

소스코드

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int[] solution(int N, int[] A) {
        // write your code in Java SE 8
        int[] counters = new int[N];    // int default = 0

        int max = 0;
        int lower_limit = 0;

        for( int i=0; i<A.length; i++ ){
            // A[i] - 1로 적용해야한다.( index값에 맞춰야함으로 )
            if( A[i]-1 < N ){
                if( counters[A[i]-1] < lower_limit ){
                    counters[A[i]-1] = lower_limit;
                }
                counters[A[i]-1] += 1;
                if( max < counters[A[i]-1] ) max = counters[A[i]-1];
            }else{
                lower_limit = max;
            }
        }

        for( int i=0; i<counters.length; i++ ){
            if( counters[i] < lower_limit ) counters[i] = lower_limit;
            else continue;
        }

        return counters;
    }
}

 

+ 더 간결하게 푸신 분의 블로그

https://ifuwanna.tistory.com/424

[Codility] Lesson4. MaxCounters - 문제풀이