[Codility(코딜리티)] Lesson4. MaxCounters (88%)

Lesson 4 Counting Elements - MaxCounters (Java Solution)

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

MaxCounters coding task - Learn to Code - Codility

---

문제

카운터 배열의 수 N과 배열 A가 주어진다

X는 1이상, N이하, k번째 카운터의 값을 1증가 한다

K가 N+1이면 모든 카운터의 값을 Max counter의 값으로 초기화 한다

 

해결

처음 풀었을 때,

생각난건 그냥 배열을 돌리면서 일반 조건에 만족하면 해당 인덱스를 1씩 증가하고,

max 조건에 걸리면 모두 Max로 초기화해주었다

정답은 맞았지만 O(N*M)으로 시간복잡도 문제에 걸렸다 

A의 길이 : M, 주어진 N 

public class MaxCounters {
    public int[] solution(int N, int[] A) {

        HashMap<Integer, Integer> X = new HashMap<>();
        int max = 0;
        putAll(X, N, 0);

        for (int i=0; i<A.length; i++) {
            if (A[i]>=1 && A[i]<=N) {
                int value = (int)X.get(A[i]) + 1;
                max = value > max ? value : max;
                X.put(A[i], value);
            } else if (A[i]==N+1) {
                putAll(X,N,max);
            }
        }

        int[] resultArr = new int[N];
        for (int i=0; i<N; i++) {
            resultArr[i] = X.get(i+1);
        }

        return resultArr;
    }

    private void putAll(Map<Integer, Integer> map, int size, int value) {
        for (int i=1; i<=size; i++) map.put(i, value);
    }
  }

성능 테스트 중에 4개가 실패했다

2번째 개선으로 자료구조를 맵 대신 배열을 이용해봤다

public class MaxCounters {

    public int[] solution(int N, int[] A) {
        int[] X = new int[N];
        int max = 0;
        putAll(X, N, 0);

        for (int i=0; i<A.length; i++) {
            if (A[i]>=1 && A[i]<=N) {
                int value = X[A[i]-1] + 1;
                max = value > max ? value : max;
                X[A[i]-1] = value;
            } else if (A[i]==N+1) {
                putAll(X,N,max);
            }
        }
        return X;
    }

    private void putAll(int[] arr, int size, int value) {
        for (int i=0; i<size; i++) arr[i] = value;
    }
  }

성능 테스트에서 2개는 해결되었지만, 여전히 성능 테스트에 2개가 걸렸다 

위의 로직 모두 O(N*M) 이다

이중 포문을 제거해야 시간복잡도를 더 줄일 수 있을 거 같았다

그래서 M을 마지막에 For문을 다 빠져나와서 한번에 돌리는 방법을 생각해보았다

 

카운터 로직을 for문 밖으로 빼는 방법으로 다시 풀었다

public class MaxCounters {

    public int[] solution(int N, int[] A) {

        int[] X = new int[N];

        int max = 0;
        int currentMax = 0;

        for (int i=0; i<A.length; i++) {
            if (A[i]>=1 && A[i]<=N) {
                int value = X[A[i]-1] + 1;
                currentMax = value > currentMax ? value : currentMax;
                X[A[i]-1] = value;
            } else if (A[i]==N+1) {
                max += currentMax;
                currentMax = 0;
                X = new int[N];
            }
        }

        for (int i=0; i<X.length; i++) {
            X[i] = X[i] + max;
        }
        
        return X;
    }
  }

Max를 따로 구해두고, Max 값을 마지막에 더해준다

시간복잡도가 O(N+M)이 나왔는데 88%이다

아직 마지막 성능 테스트를 통과하지 못했다

지금은 Max 조건일 경우, 계속 int[] A = new int[N]으로 초기화해주는데

이 초기화하는 시간을 줄여봐야겠다