Table of contents

코딜리티 MaxCounters

카운터 배열의 수 N과 배열 A가 주어진다. 배열의 각 인자 X가 갖는 범위에 따라 다음과 같은 연산이 수행된다.

  • 1 <= X <= N: k번째 카운터의 값을 1증가
  • K = N + 1: 모든 카운터의 값을 max counter의 값으로 set

배열 A를 순환하면서 위의 연산을 카운터 배열을 대상으로 실행한 뒤, 카운터 배열을 반환한다.

첫번째 풀이

77 out of 100 points (77%)

class Solution {
    int max = 0;
    
    public int[] solution(int N, int[] A) {
        int[] result = new int[N];
        for (int i = 0; i < A.length; i++) {
            int operation = A[i];
            if (operation <= N) {
                increase(result, operation - 1);
            } else if (operation == N + 1) {
                maxCounter(result);
            }

        }
        return result;
    }
    
    private void increase(int[] A, int X) {
        int val = ++A[X];
        if (val > max) {
            max = val;
        }
    }
    
    private void maxCounter(int[] A) {
        for (int i = 0; i < A.length; i++) {
            A[i] = max;
        }
    }
}

처음에는 max를 매번 계산하려다가 복잡도가 높아질 것 같아서 다른 방법을 생각해봤다.

생각해본 결과가 위의 코드인데, 카운터 값을 증가할 때마다 max값을 갱신한다. 그러나, A의 사이즈가 작은 경우의 테스트 케이스는 통과하지만, 사이즈가 큰 경우 time out에 걸려 77점이 나왔다.

그럼 여기서 어떻게 복잡도를 더 줄일 수 있을까? increase나 max를 갱신하는 부분은 더 이상 개선의 여지가 없어보인다. 그렇다면 maxCounter 메소드가 수행하는 역할을 개선해야 한다는 소린데, 감이 잡히질 않아서 스택오버플로우를 찾아봤다.

두번째 풀이 (maxCounter를 마지막에 한번만 수행하기)

스택오버플로우에서 검색을 해본 결과 해결법을 찾긴 찾았다. maxCounter를 수행하지 않고 임시로 해당 시점의 max값을 계속해서 갱신하면서 마지막에 그 max 값보다 작은 요소들만 갱신시켜주는 방법이다. 코드를 먼저 살펴보자.

private int[] maxCounters(int N, int[] A) {
    int currentMax = 0;
    int lastCalledMax = 0;
    int[] counters = new int[N];

    for (int i = 0; i < A.length; i++) {
        if (A[i] == N + 1) {
            lastCalledMax = currentMax;
        } else {
            int counter = A[i] - 1;
            if (counters[counter] < lastCalledMax) {
                counters[counter] = lastCalledMax + 1;
            } else {
                counters[counter]++;
            }

            if (counters[counter] > currentMax) {
                currentMax = counters[counter];
            }
        }
    }

    for (int i = 0; i < N; i++) {
        if (counters[i] < lastCalledMax) {
            counters[i] = lastCalledMax;
        }
    }

    return counters;
}

반환문 이전의 반복문에서 각 카운터의 카운트 값이 마지막으로 maxCounter가 호출된 시점의 max 값보다 작은 경우 해당 값으로 갱신한다. 실제 A 배열을 순환하면서 각 임시 변수를 갱신하는 부분이 조금 헷갈릴 수 있다. 우선 변수의 용도부터 살펴보자.

  • currentMax
    • 첫번째 풀이에서 increase가 수행될 떄마다 max값을 갱신하는 것과 같다.
    • 각 순환에서 현재 카운터의 값이 max값보다 크다면 currentMax에 현재 카운터의 값을 저장한다.
  • lastCalledMax
    • 첫번째 풀이에서 maxCounter가 수행하던 일을 마지막에 한번만 수행하기 위한 변수.
    • 마지막으로 maxCounter가 호출된 시점의 max 값을 저장한다.

이번엔 반복문을 살펴보자.

  1. 첫번째 if문은 K = N + 1인 경우에 해당한다.
    1. 모든 카운터의 값을 max counter의 값으로 set 해야 하지만, 복잡도를 줄이기 위해 해당 시점의 max값을 저장한다.
    2. 가장 마지막으로 maxCounter가 호출된 시점의 max 값이 가장 큰 값이 된다.
  2. 그 다음 else 문에서 다음과 같은 일을 수행한다.
    1. increase가 수행될 카운터의 값이 마지막으로 maxCounter가 호출된 시점의 max 값인 lastCalledMax보다 작은가?
      1. 작다면 해당 카운터에 lastCalledMax + 1을 저장한다.
      2. 작지 않다면 해당 카운터의 값을 1증가 시킨다.
    2. currentMax를 갱신한다.

이번엔 예제에 나온 값으로 각 과정이 어떻게 수행되는지 살펴보자.

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

N = 5이며, currentMax와 lastCalledMax의 초기 값은 0이다.

  • i = 0
    • A[i] = 3
    • 3번 카운터의 값을 1증가
    • currentMax는 1로 갱신된다.
    • counters: (0, 0, 1, 0, 0), currentMax = 1, lastCalledMax = 0
  • i = 1
    • A[i] = 4
    • 4번 카운터의 값을 1증가
    • counters: (0, 0, 1, 1, 0), currentMax = 1, lastCalledMax = 0
  • i = 2
    • A[i] = 4
    • 4번 카운터의 값을 1증가
    • currentMax는 2로 갱신된다.
    • counters: (0, 0, 1, 2, 0), currentMax = 2, lastCalledMax = 0
  • i = 3
    • A[i] = 6
    • A[i]가 N + 1 이므로 maxCounter를 수행하여 lastCalledMax 가 2로 갱신된다.
    • counters: (0, 0, 1, 2, 0), currentMax = 2, lastCalledMax = 2
  • i = 4
    • A[i] = 1
    • 1번 카운터의 값을 1증가해야 하지만, lastCalledMax가 2이므로 lastCalledMax + 1을 하여 3이 된다.
      • 실제로는 maxCounter가 수행되지 않았지만, 수행된 것처럼 간주해야 한다.
      • 마지막 maxCounter 수행 시점의 max 값이 2이므로 원래 maxCounter가 수행되었다면 1번 카운터의 값은 2일 것이며 increase가 수행되면 3이 되어야 한다.
    • counters: (3, 0, 1, 2, 0), currentMax = 2, lastCalledMax = 2
  • i = 5과 i = 6
    • A[i] = 4
    • 4번 카운터의 값을 1씩 증가시킨다.
    • counters: (3, 0, 1, 4, 0), currentMax = 4, lastCalledMax = 2

이제 마지막 부분이다. 최종 결과는 (3, 2, 2, 4, 2)가 되어야 한다. 마지막 결과값에서 lastCalledMax인 2보다 작은 부분들을 2로 갱신하면 최종 결과와 같아진다.

정리

배열의 사이즈가 범위가 큰 문제에서 (보통 10000 이상 정도인 것 같다), 내 솔루션이 해당 배열을 두 번 이상 순회한다면 하나의 순환문으로 해결할 수 없는지 고려해야할 것 같다. MissingInteger 문제에서도 그렇고, 보통 이러한 경우에 임시변수나 컬렉션을 이용하는 방법을 자주 사용하나보다.