[ Codility ] - Lesson4 MaxCounters(C++)

문제조건

• 카운터의 개수 N
• 카운팅하는 수 A

문제설명

  N개의 카운터가 주어주고 A에 정의 된 값들이 순차적으로 몇 번째 카운터를 셀지 알려줍니다. 그러다가 A의 값으로 N + 1이 나오면 모든 카운터 중에 최대값으로 나머지 카운터들을 초기화해줍니다. 그리고 마지막에 카운터 벡터를 반환하면서 프로그램을 종료하면 됩니다.

문제풀이

vector<int> solution(int N, vector<int> &A) {
    vector<int> cnt(N); 	// 카운터들
    
    int max1 = 0;		// N+1 상황에 사용할 최댓값
    int max2 = 0;		// 실질적인 카운터 최댓값
    
    for( int i = 0; i < A.size(); i++ )
    {
        if( A[i] == N + 1 ) { max1 = max2; }
        // 값이 N+1일 때, 카운터들 초기화를 위해 max1에 값을 담음
        else
        {
            cnt[A[i] - 1] = ( max1 > cnt[A[i] - 1] ) ? max1+1 : cnt[A[i] - 1]+1;
            // 카운터의 값이 최댓값 보다 작을 경우 최대값+1 아닐 경우엔 그냥 카운트
            
            if( cnt[A[i] - 1] > max2 ) { max2 = cnt[A[i] - 1]; }
            // 실질적인 최댓값을 구하는 과정
        }
    }
    
    for( int i = 0; i < N; i++ )
    {
        if( cnt[i] < max1 ) { cnt[i] = max1; }
        // 바로 초기화하지 않았기 때문에 초기화 시 최대값보다 작은 값을 최대값으로 치환
    }

    return cnt;
}

코드설명

• 값을 반환하기 위한 카운터 cnt와 상황에 따라 이용할 max변수 2개 정의
• 반복문을 돌리면서 A의 값에 따라 카운팅
  • A의 값이 N + 1일 경우에는 최대값을 max2로부터 전해받아 max1에 저장
  • 그 외의 경우에는 그냥 카운팅을 하는데, 현재 카운터가 max1보다 작은 경우 즉, 최대값으로 초기화 된 상황에서 max1 보다 커야하니 max1 + 1로 값을 정의해줍니다.
• 마지막 반복문은 N + 1상황에서 max1에 저장만 해뒀던 값을 실제로 적용해주는 역할입니다.
• 마지막으로 return cnt로 카운터의 값들을 반환해주며, 끝내줍니다.

결과사진